# 6. Binary Tree

## Preorder

*Recursive*

```java
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*

```java
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*

```java
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)

```python
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*

```java
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

```python
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*

```java
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

```java
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);
}
```

```java
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;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/binary_tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.