6. Binary Tree

Preorder

Recursive

List<Integer> preorderTraversal(TreeNode root) {
  List<Integer> result = new ArrayList<>();
  preorder(root, result);
  return result;
}

private void preorder(TreeNode root, List<Integer> result){
    if (root == null){
        return;
    }
    result.add(root.val);
    preorder(root.left, result);
    preorder(root.right, result);
}

Divide & conquer

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null){
        return result;
    }

    List<Integer> left = preorderTraversal(root.left);
    List<Integer> right = preorderTraversal(root.right);

    result.add(root.val);
    result.addAll(left);
    result.addAll(right);

    return result;
}

Iterative

public List<Integer> preorderTraversal(TreeNode root) {
    Deque<TreeNode> queue = new LinkedList<>();
    List<Integer> result = new ArrayList<>();

    if(root == null){
        return result;
    }

    queue.push(root);

    while(!queue.isEmpty()){
        TreeNode node = queue.pop();
        result.add(node.val);
        if (node.right != null){
            queue.push(node.right);
        }
        if (node.left != null){
            queue.push(node.left);
        }
    }
    return result;
}

Morris

• Save space but traverse the nodes twice

• Time O(n)

def morrisInorder(root):
  def findPredecessor(node):
    pre = node.left
    while cur.right and cur.right != node:
      pre = pre.right
    return pre
  
  cur = root
  while cur:
    if cur.left:
      # find the rightest node in left subtree
      pre = findPredecessor(cur)
      # first traverse
      if not pre.right:
        pre.right = cur
        cur = cur.left
      # 2nd traverse
      else:
        pre.right = None
        print(cur.val)
        cur = cur.right
    else:
      print(cur.val)
      cur = cur.right

Inorder

• Create TreeNode cur

• 2 whiles, first put node to left bottom

Iterative

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();

    TreeNode cur = root;

    while(cur != null || !stack.isEmpty()){
        while(cur != null){
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        result.add(cur.val);
        cur = cur.right;
    }
    return result;
}

O(1) Space

while node:
  while node.left and pre != node.left:
    node = node.left
    
  print(node.val)
  
  if node.right:
    node = node.right
  else:
    # 從right child leaf 退回
    while node.parent.right == node:
      node = node.partent
    # 從left child leaf 退回
    pre = node
    node = node.parent

Postorder

• Create TreeNode pre & cur to compare

• Push cur in stack

Iterative

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();

    if (root == null){
        return result;
    }

    TreeNode pre = null;
    TreeNode cur = root;

    stack.push(cur);

    while(!stack.isEmpty()){
        cur = stack.peek();
        // traverse down
        if (pre == null || pre.right == cur || pre.left == cur){
            if (cur.left != null){        // has left child
                stack.push(cur.left);
            }else if (cur.right != null) {   // no left child
                stack.push(cur.right);
            }
        }else if (cur.left == pre){ // traverse up from left child
            if (cur.right != null){
                stack.push(cur.right);
            }
        }else{                      // traverse up form right child
            result.add(cur.val);
            stack.pop();
        }
        pre = cur;
    }
    return result;

Stack -> Queue

E.X. isBinarySearchTree

• Create a class and put in queue

public static boolean isBST(BinaryTreeNode<Integer> tree){
  return inRange(tree, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private static boolean inRange(BinaryTreeNode<Integer> tree, Integer lower, Integer upper){
  if (tree == null){
    return true;
  }

  if ( tree.data < lower || tree.data > upper){
    return false;
  }

  return inRange(tree.left, lower, tree.data) && inRange(tree.right, tree.data, upper);
}

private static class node{
  public BinaryTreeNode<Integer> nodeTree;
  public Integer lower, upper;

  public node(BinaryTreeNode<Integer> nodeTree, Integer lower, Integer upper){
    this.nodeTree = nodeTree;
    this.lower = lower;
    this.upper = upper;
    }
  }
public static boolean isBST(BinaryTreeNode<Integer> tree){
  Queue<node> q = new LinkedList<>();
  q.add(new node(tree, Integer.MIN_VALUE, Integer.MAX_VALUE));
  node head;
  while((head = q.poll()) != null){
    if (head.nodeTree == null){
        return true;
    }
    if ( head.nodeTree.data < head.lower || head.nodeTree.data > head.upper){
        return false;
    }

    q.add(new node(head.nodeTree.left, head.lower, head.nodeTree.data));
    q.add(new node(head.nodeTree.right, head.nodeTree.data, head.upper));
  }
  return true;
}