Post Order traversal of a binary tree

Question

I'm learning to code he tree traversals of the binary tree. So far, I've come up with this from many tutorials on the net. However, when I try to do any traversal, I am running into an infinite loop. Where am I going wrong?

class Node {
int value;
String name;

Node lchild = null;
Node rchild = null;

Node(int key, String name) {
    this.value = key;
    this.name = name;
    }
}

public class genTrees {

Node root;

public void addNode(int key, String s) {
    Node newnode = new Node(key, s);
    if (root == null) {
        System.out.println("Added Root");
        root = newnode;
    } else {
        Node focusNode = root;
        Node parent;
        while (true) {
            parent = focusNode;
            if (key <= focusNode.value) {
                focusNode = focusNode.lchild;
                if (focusNode == null) {
                    System.out.println("Added on Left" + key);
                    parent.lchild = newnode;
                    return; // All done
                }
            }
            if (key > focusNode.value) {
                focusNode = focusNode.rchild;
                if (focusNode == null) {
                    System.out.println("Added on Right" + key);
                    parent.rchild = newnode;
                    return;
                }
            }
        }
    }
}

void inOrder(Node n) {
    while (n != null) {
        inOrder(n.lchild);
        System.out.println(n);
        inOrder(n.rchild);
    }
}

Thanks!

Answer 1

The following loop:

while (n != null) {
    inOrder(n.lchild);
    System.out.println(n);
    inOrder(n.rchild);
}

will run forever if n == null. And will keep on calling the recursive method on each iteration. Perhaps, you should change it to:

if (n != null) {
    inOrder(n.lchild);
    System.out.println(n);
    inOrder(n.rchild);
}