unable to do preorder traversal in BST

Viewed 60

Question : Given the root of a binary tree, return the preorder traversal of its nodes values.

I solved this using iterative way, where I had used 'top.state++' instead to 'state++' and I got my answer. But unable to get answer when I was using 'state++'. Can anyone tell me why is it so?

class Solution {
    class Pair {
        TreeNode root;
        int state;
        Pair(TreeNode root,int state) {
            this.root = root;
            this.state = state;
        }
    }
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> al = new ArrayList<>();
        if(root == null) return al;
        Stack<Pair> stack = new Stack<>();
        stack.push(new Pair(root,1));
        while(!stack.isEmpty()) {
            Pair top = stack.peek();
            int state = top.state;
            TreeNode curr = top.root;
            
            if(state == 1) {
                al.add(curr.val);
                top.state++; // why top.state++, why not state++ ?
                if(curr.left != null) stack.push(new Pair(curr.left,1));
            }
            else if(state == 2) {
                top.state++;
                if(curr.right != null) stack.push(new Pair(curr.right,1));
            }
            else {
                stack.pop();
            }
        }
       return al;
    }
}
3 Answers

Because int state = top.state is a local variable that copies the value of top.state. It does not share the same location in memory. Therefore, changing the value of the local variable will not change the value of the top.state field.

See this for more information https://java-programming.mooc.fi/part-5/3-primitive-and-reference-variables

Declaring a primitive variable causes the computer to reserve some memory where the value assigned to the variable can be stored. The size of the storage container reserved depends on type of the primitive. In the example below, we create three variables. Each one has its own memory location to which the value that is assigned is copied.

int first = 10;
int second = first;
int third = second;
System.out.println(first + " " + second + " " + third);
second = 5;
System.out.println(first + " " + second + " " + third);

Which prints:

10 10 10
10 5 10

The name of the variable tells the memory location where its value is stored. When you assign a value to a primitive variable with an equality sign, the value on the right side is copied to the memory location indicated by the name of the variable. For example, the statement int first = 10 reserves a location called first for the variable, and then copies the value 10 into it.

Similarly, the statement int second = first; reserves in memory a location called second for the variable being created and then copies into it the value stored in the location of variable first.

You need to maintain the state variable in the pair object . This value is reassigned each time through the loop using state++, so it not works.

But I don't understand why you need a Pair object to do this traversal. Simple way:

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                result.add(root.val);
                stack.push(root);
                root = root.left;
            } else {
                TreeNode pop = stack.pop();
                root = pop.right;
            }
        }
        return result;
    }

You're working way too hard. A good way to find iterative algorithms is to start with the recursive version and transform.

void preorder(TREE t) {
  if (t != null) {
    list.add(t.val);
    preorder(t.left);
    preorder(t.right);
  }
}

Assume Java has goto. We'll get rid of these later. First remove the tail recursion:

void preorder(Tree t) {
START:
  if (t != null) { 
    list.add(t.val);
    preorder(t.left);
    t = t.right;
    goto START;
  }
}

Now "simulate" the recursive call by saving local variables (here just t) on a stack, replacing the arguments (here just t again), then using goto to do the same things the compiled code would with call/return instructions.

void preorder(Tree t) {
START:
  if (t != null) { 
    list.add(t.val);
    stack.push(t);
    t = t.left; // Simulate the call.
    goto START;
RETURN:         
    t = t.right;
    goto START;
  }
  if (!stack.isEmpty()) { // Simulate the return.
    t = stack.pop();
    goto RETURN;
  }
}

Now we'll transform to get rid of the gotos. First notice that goto RETURN can be eliminated by code motion.

void preorder(Tree t) {
START:
  if (t != null) { 
    list.add(t.val);
    stack.push(t);
    t = t.left;
    goto START;    
  }
  if (!stack.isEmpty()) {
    t = stack.pop();
    t = t.right;
    goto START;
  }
}

This is just two nested loops. The top if is just a while loop in disguise:

void preorder(Tree t) {
START:
  while (t != null) { 
    list.add(t.val);
    stack.push(t);
    t = t.left;
  }
  if (!stack.isEmpty()) {
    t = stack.pop();
    t = t.right;
    goto START;
  }
}

The remaining loop runs the entire function body until the stack is empty and breaks out as soon as this happens:

void preorder(Tree t) {
  for (;;) {
    while (t != null) { 
      list.add(t.val);
      stack.push(t);
      t = t.left;
    }
    if (stack.isEmpty()) break;
    t = stack.pop();
    t = t.right;
  }
}

Now we can clean this up to make real Java.

List<Integer> preorder(Tree t) {
  List<Integer> list = new ArrayList<>();
  Deque<Tree> stack = new ArrayDeque<>();
  for (;;) {
    while (t != null) { 
      list.add(t.val);
      stack.push(t);
      t = t.left;
    }
    if (stack.isEmpty()) break;
    t = stack.pop();
    t = t.right;
  }
  return list;
}

The nice thing about this is the zero reasoning about how the stack works. There's only algebra on code. After you've practiced a bit, it's not hard.

It's stacking the nodes that have already been visited then plunging immediately down to the left. That means the stack holds nodes waiting for their right children to be visited, which is exactly what happens after the pop. But, I'm only discovering this after the code is already done.

Related