Iterate through binary search tree to find all leaves

java algorithm iterator nodes binary-search-tree
Sti picture Sti · Nov 5, 2012 · Viewed 36.8k times · Source

I am pretty new to trees, and I am trying to create kind of a "leaf iterator". I'm thinking it should put all nodes that does not have a .left and .right value onto a stack, but I'm not sure how or even if it's the right thing to do. I have tried searching for it, but every example I come over starts with going to the leftmost leaf, and going p = node.parent, and I am avoiding linking to the node's parent.

I don't understand how I can repeatedlty start from the root and go through the vines without visiting the same vines over and over.

EDIT

I see people suggests using a recursive method to solve this, and I agree now. But I have been banging my head trying to find the solution for an iterator-class-way to do this for a while, and I still would like to know if that's possible, and how!

Answer

Tomasz Nurkiewicz picture Tomasz Nurkiewicz · Nov 5, 2012

Use recursion:

public void visitNode(Node node) {
    if(node.left != null) {
        visitNode(node.left);
    }
    if(node.right != null) {
        visitNode(node.right);
    }
    if(node.left == null && node.right == null) {
        //OMG! leaf!
    }
}

start it by supplying root:

visitNode(root);

In order to translate this into an Iterator<Node> you'll have to translate recursion to loop and then to traversal with state. Non-trivial, but should give you a lot of fun.

Related questions

In-order iterator for binary tree

How can I write a Java iterator (i.e. needs the next and hasNext methods) that takes the root of a binary tree and iterates through the nodes of the binary tree in in-order fashion?

Read More
Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More
Generating all permutations of a given string

What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?

Read More