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

• 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

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

• 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;
        
    }