Binary Traverse

pre-order
void traverse(Node p) {
  if (p == null) return;
 
  System.out.println(p.data);
 
  traverse(p.left);
  traverse(p.right);
 
}
non-recursive
void traverse() {
  Stack<Node> stack = new Stack<Node>();
  stack.push(root);
 
  while (!stack.empty()) {
     Node node = stack.pop();
 
     if (node != null) {
        System.out.println(node.data);
 
        stack.push(node.right);
        stack.push(node.left);
     }
  }
}
in-order
void traverse(Node p) {
  if (p == null) return;
 
  traverse(p.left);
 
  System.out.println(p.data);
 
  traverse(p.right);
 
}
non-recursive
void traverse() {
  Stack<Node> stack = new Stack<Node>();
 
  Node current = root;
  boolean done = false; 
 
  while (!done) {
     if (current) {
        stack.push(current);
        current = current.left;
     } else {
        if (stack.isEmpty()) {
          done = true; 
        } else {
       Node node = stack.pop();   
       System.out.println(node.data);
       current = node.right;
        }
     }
  } 
 
}
post-order
void traverse(Node p) {
  if (p == null) return;
 
  traverse(p.left);
  traverse(p.right);
 
  System.out.println(p.data);
 
}
non-recursive
  • using two pointers
void traverse() {
  Stack<Node> stack = new Stack<Node>();
  stack.push(root);
 
  Node pre = null;
 
  while (!stack.isEmpty()) {
     Node current = stack.top();
     // we are traversing down the tree
     if (pre == null || pre.left == current || pre.right == current) {
         if (current.left) {
            stack.push(current.left);
         } else if (current.right) {
            stack.push(current.right);
         } else {
            System.out.println(current.data);
            stack.pop();
         }
     }
 
     // we are traversing up the tree from the left
     if (current.left == pre) {
        if (current.right) {
           stack.push(current.right);
        } else {
           System.out.println(current.data);
            stack.pop();
        }   
     }
 
     // we are traversing up the tree from the right
     if (current.right == pre) {
         System.out.println(current.data);
         stack.pop();
     }
 
     pre = current;
 
}
  • using two stack approach
void traverse() {
  Stack<Node> stack1 = new Stack<Node>();
  stack1.push(root);
 
  Stack<Node> stack2 = new Stack<Node>();
 
  while (!stack1.isEmpty()) {
     Node node = stack1.pop();
     stack2.push(node);
 
     if (node.left) {
        stack1.push(node.left);
     } 
 
     if (node.right) {
       stack1.push(node.right);
     }
  } 
 
  while(!stack2.isEmpty()) {
     Node node = stack2.pop();
     System.out.println(node.data); 
  }
}
Add a New Comment
or Sign in as Wikidot user
(will not be published)
- +
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License