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


---

# 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://jenhsuan.gitbook.io/algorithm/algorithms-in-a-nutshell/binary-search-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.