Traversing through all nodes of a binary tree in Java

Question

Let's say I have a simple binary tree node class, like so:

public class BinaryTreeNode {
    public String identifier = "";
    public BinaryTreeNode parent = null;
    public BinaryTreeNode left = null;
    public BinaryTreeNode right = null;

    public BinaryTreeNode(BinaryTreeNode parent, String identifier)
    {
        this.parent = parent; //passing null makes this the root node
        this.identifier = identifier;
    }

    public boolean IsRoot() {
        return parent == null;
    }
}

How would I add a method which is able to recursively traverse through any size tree, visiting each and every existing node from left to right, without revisiting a node that has already been traversed?

Would this work?:

public void traverseFrom(BinaryTreeNode rootNode)
{
    /* insert code dealing with this node here */

    if(rootNode.left != null)
        rootNode.left.traverseFrom(rootNode.left);

    if(rootNode.right != null)
        rootNode.traverseFrom(rootNode.right);
}

@PeterWooster - right, except that I am calling the traverse method from each node, causing recursion to occur recursively for each node instead of from just the root — RectangleEquals
– RectangleEquals, Commented Mar 9, 2013 at 3:38

codeMan · Accepted Answer · 2013-03-09 02:32:08Z

39

There are 3 types of Binary tree traversal that you can achieve :

example:

consider this following Binary tree :

enter image description here

Pre-order traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)
In-order traversal sequence: A, B, C, D, E, F, G, H ,I (left, root, right)
Post-order traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)

code example:

left to right traversal of the Binary tree, nay In order Traversal of binary tree :

public void traverse (Node root){ // Each child of a tree is a root of its subtree.
    if (root.left != null){
        traverse (root.left);
    }
    System.out.println(root.data);
    if (root.right != null){
        traverse (root.right);
    }
}

edited Mar 9, 2013 at 2:32

answered Mar 9, 2013 at 2:25

codeMan

5,7603 gold badges29 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Peter Wooster Over a year ago

+1, Recursion is always the answer for trees. The interesting answer is to do this without recursion.

codeMan Over a year ago

@Peter Wooster Iterative solution is little more harder to understand especially for beginners, so I thought why make complications.

Peter Wooster Over a year ago

I agree, I wrote something like that in assembler years ago, it used a stack of course.

RectangleEquals Over a year ago

I knew I was close, but also that something was a little wrong. Thanks for filling me in, and +1 for the education

codeMan Over a year ago

@Peter Wooster you did that in asm?? RESPECT!!

RouteMapper · Accepted Answer · 2013-03-09 02:42:02Z

9

codeMan is right. The traversal will visit every node on the left. Once it reaches the last node on the left, it begins working its way back along the right-side nodes. This is a depth-first search (DFS) traversal. As such, each node is visited only once, and the algorithm runs in O(n) time. Happy coding.

edited Mar 9, 2013 at 2:42

answered Mar 9, 2013 at 2:29

RouteMapper

2,5601 gold badge30 silver badges48 bronze badges

Collectives™ on Stack Overflow

Traversing through all nodes of a binary tree in Java

2 Answers 2

5 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related