CODEWITHSUNDEEP
javadata-structuresbinary-tree
user1235720
user1235720

Reputation:

Iteratively accessing all binary tree nodes?

I have a Binary Tree which has a word on each node.

In another Class I need to access the nodes one by one and then manipulate the words. What is the best way to access the nodes one by one from another class?

In my BinaryTree Class each node has a leftchild, rightchild and a value(String). I have three methods, printinorder, insert and findnode. The find node takes in a string and sees if that string is stored in any of the node values.

public void printInOrder(Node node) {
    if (node != null) {
        printInOrder(node.left);
        System.out.println(node.value);
        printInOrder(node.right);
    }

I have another class and need to get at the nodes one by one but I am not sure whats the best way of doing it from another class. I am able to traverse the tree from within the class but not from a different class.

Upvotes: 0

Views: 2176

Answers (4)

Brenden Brown
Brenden Brown

Reputation: 3225

Read templatetypedef's answer, which is a more efficient approach. The advantage of the approach I present is that it does not require any changes to your existing Node class, and uses the same pattern you've already used for PrintInOrder. It only relies upon public properties of the Node class, so should be useable from a separate class.

public List<Node> nodes GetAllNodes(Node root) {
    List<Node> nodes = new ArrayList<Node>();
    if (root != null) {
        nodes.addAll(GetAllNodes(root.left));
        nodes.add(root);
        nodes.addAll(GetAllNodes(root.right));
    }
    return nodes;
}

I didn't compile or test this, so there may be errors.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372952

One way to walk over all the nodes in a binary tree is to do the following, which starts the leftmost node and repeatedly migrates to the current node's inorder successor:

  1. Start by walking as far to the left as you possibly can without falling off the tree. This is your first node.

  2. To get from one node to the next one that should be visited, do the following:

    1. If the node has a right child, descend to the right child, then continuously descend to the left child as far as possible. You end at the next node to visit.
    2. Otherwise, repeatedly walk upward from the node to its parent until you walk up an edge from a left child to its parent. Where you end up is the new node.

This ends up taking only O(n) time across all nodes, so it's a very fast way to migrate between nodes.

In order for this to work, you will either need to have each node store a parent pointer or will have to maintain a stack of the path of nodes from the start node downward to the current node. However, for reasonably balanced trees, this is much more space efficient than populating an entire list of the nodes in the tree and returning it.

Hope this helps!

Upvotes: 1

Kent
Kent

Reputation: 195169

For searching :

You could sort your tree to a binary search tree. Or when you were building the tree, build a binary search tree. It would be the best way to search. O(logn) .

The search should be implemented in your findNode(String value) method

or you have problem to implement the search?

Upvotes: 0

TheoretiCAL
TheoretiCAL

Reputation: 20571

Assuming you have a tree class, write first a method that traverses the tree first (breadth/depth search). At every node in the traversal, assuming your nodes are some type of object that holds a word in one of its variables, access the node and change the stored word. Basically write functions in your Binary Tree class that let you do this, and call them in your other class.

Upvotes: 0

Related Questions