Counting the number of nodes in Leaf diagram

Question

Been working on this for while with no luck. Hopefully someone can point in the right direction.

Code:

public class BST {
  public BTNode<Integer> root;
  int nonLeafCount = 0;
  int depthCount = 0;

  public BST() {
    root = null;
  }



  class BTNode<T> {
    T data;
    BTNode<T> left, right;

    BTNode(T o) {
      data = o;
      left = right = null;
    }

    public String toString() {
      return String.valueOf(data);
    }
  }
}

Answer 1

The easy way to traverse a tree without recursive calls is to use a stack. Push the root on the stack, then enter a loop that - so long as the stack is not empty - pops a node from the stack and pushes the non-null children of that node. It's pretty obvious that this will eventually push every node onto the stack exactly once and pop it exactly once. Now all you need to do is count the popped nodes that have at least one child. Putting this together,

public int nonleaves() {
  int nonLeafCount = 0;
  BTNode<Integer> [] stack = new BTNode[2];
  int p = 0;
  stack[p++] = root; // push root
  while (p != 0) {
    BTNode<Integer> node = stack[--p]; // pop
    if (node.left != null || node.right != null) ++nonLeafCount;
    if (p + 1 >= stack.length) stack = Arrays.copyOf(stack, 2 * stack.length);
    if (node.right != null) stack[p++] = node.right; // push right
    if (node.left != null) stack[p++] = node.left;   // push left
  }
  return nonLeafCount;
}

Note that in accordance with your description, I used a simple Java array for a stack, growing it by a factor of 2 whenever it fills up. Integer p is the stack pointer.

Also, this code assumes the root is non-null. If the root can be null, add a check at the start and return 0 in that case.

NB it's possible to traverse without even a stack by several methods, although at the cost of changing the tree during traversal. (It's back in its original shape when the traversal is complete.) The nicest IMO is Morris's algorithm, but all of them are considerably more complicated than the stack. Since it seems you're a new programmer, figure out the stack method first.

Edit

To find max depth:

public int maxDepth() {
  int max = 0;
  Pair<Integer> [] stack = new Pair[2];
  int p = 0;
  stack[p++] = new Pair(root, 1);
  while (p != 0) {
    Pair<Integer> pair = stack[--p];
    if (pair.depth > max) max = pair.depth;
    if (p + 1 >= stack.length) stack = Arrays.copyOf(stack, 2 * stack.length);
    if (pair.node.right != null) 
      stack[p++] = new Pair(pair.node.right, 1 + pair.depth);
    if (pair.node.left != null) 
      stack[p++] = new Pair(pair.node.left, 1 + pair.depth);
  }
  return max;
}

private static class Pair<T> {
  BTNode<T> node;
  int depth;
  Pair(BTNode<T> node, int depth) {
    this.node = node;
    this.depth = depth;
  }
}

Finally, I'd be remiss if I didn't point out that we can do some algebra on the algorithm to eliminate some tiny inefficiencies. You'll note that after the left child is pushed onto the stack, it is certain to be popped in the next loop iteration. The root push/pop is similar. We might as well set node directly. Also, there are some redundant comparisons. The details are too much for this note, but here is a reworked non-leaf counter (untested but ought to work fine):

public int nonleaves() {
  int nonLeafCount = 0;
  BTNode<Integer>[] stack = new BTNode[1];
  int p = 0;
  BTNode<Integer> node = root;
  for (;;) {
    if (node.left == null) {
      if (node.right == null) {
        if (p == 0) break;
        node = stack[--p];
      } else { // node.right != null
        ++nonLeafCount;
        node = node.right;
      }
    } else { // node.left != null
      ++nonLeafCount;
      if (node.right != null) {
        if (p >= stack.length) {
          stack = Arrays.copyOf(stack, 2 * stack.length);
        }
        stack[p++] = node.right;
      }
      node = node.left;
    }
  }
  return nonLeafCount;
}

You can see that to eek out a tiny bit of efficiency we lose a lot of simplicity. This is almost always a bad bargain. I recommend against it.

Answer 2

A possible solution:

public class BST<T> {
    public BTNode<T> root;
    int depthCount = 0;

    public BST() {
        root = null;
    }

    public int nonleaves() { // Method must be declared like this. No
                                // parameters.
        BTNode<T> current = root;
        BTNode<T> previous = null;
        int nonLeafCount = 0;

        while (current != null) {
            if (previous == current.parent) { // this includes when parent is
                                                // null, i.e. current is the
                                                // root.
                previous = current;
                if (current.left != null) {
                    nonLeafCount++;
                    current = current.left;
                } else if (current.right != null) {
                    nonLeafCount++;
                    current = current.right;
                } else {
                    current = current.parent;
                }
            } else if (previous == current.left) {
                previous = current;
                if (current.right != null) {
                    current = current.right;
                } else {
                    current = current.parent;
                }
            } else {
                // previous==current.right
                previous = current;
                current = current.parent;
            }
        }
        return nonLeafCount;
    }

    private static class BTNode<T> {
        BTNode<T> left, right, parent;

        /* ... */
    }
}

Using stacks:

public class BST2<T> {
    public BTNode<T> root;
    int depthCount = 0;

    public BST2() {
        root = null;
    }

    public int nonleaves() { // Method must be declared like this. No
                                // parameters.
        BTNode<T> current = root;
        BTNode<T> previous = null;
        int nonLeafCount = 0;

        MyStack myStack = new MyStack(); // New empty stack

        while (current != null) {
            if (previous == myStack.top()) { // this includes when stack is 
                                                // empty, i.e. current is the
                                                // root.
                myStack.push(current);
                previous = current;
                if (current.left != null) {
                    nonLeafCount++;
                    current = current.left;
                } else if (current.right != null) {
                    nonLeafCount++;
                    current = current.right;
                } else {
                    myStack.pop();
                    current = myStack.top();
                }
            } else if (previous == current.left) {
                previous = current;
                if (current.right != null) {
                    current = current.right;
                } else {
                    myStack.pop();
                    current = myStack.top();
                }
            } else {
                // previous==current.right
                previous = current;
                myStack.pop();
                current = myStack.top();
            }
        }
        return nonLeafCount;
    }

    private static class BTNode<T> {
        BTNode<T> left, right;

        /* ... */
    }
}