Search code examples
javarecursiontreetraversal

Convert an original binary tree to have it's decorates as the preorder indexes


I've had a go, and it works for the left subtree but not the right.

I'm close but my logic is wrong, can anyone help correct and explain the logic to this.

public static MyNode preOrderNumbering(MyNode n) {
            if (n != null) {
                n.obj = 0; // Set root decoration to 0;
                preOrderHelper(n, 1); // Set decorations according to preorder.
            }
            return n;
        }

        public static MyNode preOrderHelper(MyNode n, int counter) {
            if (n != null) {
                if (n.left != null) {
                    n.left.obj = counter++; // Set the left object decoration to current count + 1;
                    preOrderHelper(n.left, counter);
                }
                if (n.right != null) {
                    n.right.obj = counter++; // Set the left object decoration to current count + 1;
                    preOrderHelper(n.right, counter);
                }
            }
            return n;
        }

Before: http://puu.sh/2k2H7.png

After: enter image description here


Solution

  • You need to update the counter with everything that's discovered on the left before going to the right.

    Something like this:

    public static int preOrderNumbering(MyNode n, int count){
        if(n != null){
            n.obj = ++count;
    
            count = preOrderNumbering(n.left, count);
            count = preOrderNumbering(n.right, count);
    
        }
        return count;
    }