> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/binary-search-tree.md).

# Binary search tree

## 1.Introduction

* Each node in the **left** sub-tree of that node has a value **less than or equal to** the value of the node
* Each node in the **right** sub-tree of that node has a value **larger than or equal to** the value of the node
* Binary search tree are typically used for fast insertion and fast lookup
* all left descendents <= n < all right descendents

## 2.Balanced v.s. Unbalanced

* Balanced不一定只有左右子樹的size相同, 需再了解紅黑樹(red-black trees), AVL tree
* 以下為balanced tree的種類
  1. Completed tree: child node先由左邊填起
  2. Full binary tree:0或2個child node
  3. Perfect tree:Completed tree + Full binary tree

## 3.Insertion

* In a tree when a new code is added there is exactly one place that it can be
* The structure of the tree depends  on the order in which the nodes are added
* The complexity for node insertion is O(Log n) in the average case
* The actual complexity depends on the shape of the tree - **skewed trees** (IE. with all left or right children only) can have complexity of O(n)
* **跟head比大小, 小-> 跟左子繼續比; 大->跟右子繼續比, 當child為NULL時insert**

```
public static Node<Integar> insert(Node<Integar> head, Node<Integar> node)
{
    if (head == null)
    {
        return node;
    }
    
    if (node.getData() <= head.getData())
    {
        head.setLeftChild(insert(head.getLeftChild(), node));
    }
    else
    {
        head.setRightChild(insert(head.getRightChild(), node));
    }
}
```

## 4.Lookup

* While searching for a node in the tree there is only one place where that node can be found
* We can simply follow the right or left sub-trees based on the value we want to find
* The complexity for node lookup is O(Log n) in the average case

```
public static Node<Integar> Lookup(Node<Integar> head, int data)
{
    if (head == null)
    {
        return nodenull;
    }
    
    if (head.getData() == data)
    {
        return head;
    }
    
    if (data <= head.getData())
    {
        return Lookup(head.getLeftChild(), data);
    }
    else
    {
        return Lookup(head.getRightChild(), data);
    }
}
```

## 5.Minimum value in BST

```
public static int minimumValue(Node<Integar> head)
{
    if (head == null)
    {
        return Integar.MIN_VALUE;
    }
    
    if (head.getLeftChild() == null)
    {
        return head.getData();
    }
    
    return minimumValue(head.getLeftChild());
}
```

## 6.Maximum depth of a binary tree

```
public static int maxDepth(Node root)
{
    if (root == null)
    {
        return 0;
    }
    
    if (head.getLeftChild() == null && head.getRightChild() == null)
    {
        return 0;
    }
    
    int leftMaxDepth = 1 + maxDepth(root.getLeftChild());
    int rightMaxDepth = 1 + maxDepth(root.getRightChild());
    
    return Math.max(leftMaxDepth, rightMaxDepth);
}
```

## 7.Mirror a binary tree

```
public static void mirror(Node<Integer> root)
{
    if (root == null)
    {
        return;
    }
    mirror(root.getLeftChild());
    mirror(root.getRightChild());
    
    Node<Integer> temp = root.getLeftChild();
    root.setLeftChild(root.getRightChild());
    root.setRightChild(temp);
}

```

## 8.Finding the structurally unique trees

* [x] [**96. Unique Binary Search Trees**](https://jenhsuan.gitbook.io/algorithm/leetcode/96.-unique-binary-search-trees)
* [ ] When the number of nodes is 1 there is just one possible tree- this is the base case
* [ ] Consider that every node can be the root - the nodes before it will be on the left and the nodes after it on the right

```
public static int countTrees(int numNodes)
{
    if (numNodes <= 1)
    {
        return 1;
    }
    
    int sum = 0;
    for (int i = 1; i <= numNodes; i++)
    {
        int countLeftTrees = countTrees(i - 1);
        int countRightTrees = countTrees(numNodes - 1);
        sum = sum + (countLeftTrees * countRightTrees); 
    }
    
    return sum;
}
```

## 9.Print all nodes within a range in a binary search tree

* L -> V -> R

```
public static void printRange(Node<Integer> root, int low, int high)
{
    if (root == null)
    {
        return;
    }
    
    if (low <= root.getData())
    {
        printRange(root.getLeftChild(), low, high);
    }
    
    if (low <= root.getData() && root.getData() <= high)
    {
        System.out.println(root.getData());
    }
    
    if (high > root.getData())
    {
        printRange(root.getRightChild(), low, high);
    }
}
```

## 10.Check if a binary search tree &#x20;

```
public static boolean isBinarySearchTree(Node<Integer> root, int min, int max)
{
    if (root == null)
    {
        return true;
    }
    
    if (root.getData() <= min || root.getData() > max)
    {
        return false;
    }
    
    return isBinarySearchTree(root.getLeftChild(), min, root.getData()) &&
                 isBinarySearchTree(root.getRightChild(), root.getData(), max) 
}
```

## 11.Path sum

```
public static boolean hasPathSum(Node<Integer> root, int sum)
{
    if (root.getLeftChild() == null &&
        root.getRightChild() == null)
    {
        return sum == root.getData();
    }
    
    int subSum = sum - root.getData();
    if (root.getLeftChild() != null &&
        hasPathSum(root.getLeftChild(), subSum))
    {
        return true;
    }
    
    if (root.getRightChild() != null &&
        hasPathSum(root.getRightChild(), subSum))
    {
        return true;
    }
    return false;
}
```

## 12.Print all paths

```
public static boolean printPaths(Node<Integer> root, List<Node<Integer>> pathList)
{
    if (root == null)
    {
        return;
    }
    
    pathList.add(root);
    printPaths(root.getLeftChild(), pathList);
    printPaths(root.getRightChild(), pathList);
    
    if (root.getLeftChild() == null &&
        root.getRightChild() == null)
    {
        print(pathList);
    }
    
    
    pathList(root);
}
```

## 13.Least common ancestor

* [x] &#x20;[236. Lowest Common Ancestor of a Binary Tree](https://jenhsuan.gitbook.io/algorithm/leetcode/236.-lowest-common-ancestor-of-a-binary-tree)

```
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL)
        {
            return NULL;
        }
        
        if (root == p || root == q)
        {
            return root;
        }
        
        TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
        TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);
        
        if (leftLCA != NULL && rightLCA != NULL)
        {
            return root;
        }
        
        if (leftLCA != NULL)
        {
            return leftLCA;
        }
        return rightLCA;
        
    }
```