Definition

A tree is a data structure used to simulate a hierarchical tree structure. Each node of a tree will have a root value and a list of references to other nodes which are called children. From a graph view, a tree can also be defined as a directed acyclic graph that has n nodes and n-1 edges.

A binary tree is a tree in which each node has at most two children, which are referred to as the left and the right child.

Traversal

• Pre-order: root, left subtree, then right subtree: F, B, A, D, C, E, G, I, H
• In-order: left, root, right: A, B, C, D, E, F, G, H, I
• Post-order: left, right, root: A, C, E, D, B, H, I, G, F

Breadth-First Search - level order traversal:

F, B, G, A, D, I, C, E, H Root, first level, second level...

Typically implemented using a queue. The idea is that at each cycle, you process the children in the queue and add the grand children to the queue. You only process as many children as the ones that were in the queue by keeping track of the queue size.

add root to q
while (!q.empty) {
    size = q.size;
    currLevel = list; 
    for (int i = 0; i < size; i++) {
    // The first time size is 1 (only root), then 2 (root l and r, and so on)
        el = q.poll;
        currLevel.add(el)
        add left to q;
        add right to q;
    }
}

Recursion and Trees

Top-down solution

Kind of pre-order. Visit the node, come up with some values, and pass them to children.

1. return for null node
2. update the answer if needed
3. left_answer = top-down (root.left, left.param)
4. right_...
5. return the answer if needed

Example: find max deep

1. return if the root is null
2. if the root is leaf:
3.    answer = max (answer, depth)
4. max_depth (left, depth + 1)
5. max_depth (right, depth +1)

Bottom-up solution

In this case, we fist call the recursive function for all the children (kind of postorder)

1. return the answer for null
2. left_Answer = bottom_up(left)
3. right_answer = bottom_up(right)
4. return answers.

Example: find max deep

1. return 0 if root is null                 // return 0 for null node
2. left_depth = maximum_depth(root.left)
3. right_depth = maximum_depth(root.right)
4. return max(left_depth, right_depth) + 1  // return depth of the subtree rooted at root

Binary Search Tree (BST)

A Binary Search Tree is a special form of a binary tree.

• The value in each node must be greater than (or equal to) any values in its left subtree
• The value in each node must be less than (or equal to) any values in its right subtree.

It is noteworthy that inorder traversal in BST will be in ascending order. Therefore, the inorder traversal is the most frequent used traversal method of a BST.

Valid BST - In order traversal

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        return validBST(root, null, null);
    }
    
    boolean validBST (TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return true;
        }
        
        // Check if the current node's value is within the valid range
        if ((min != null && node.val <= min) || (max != null && node.val >= max)) {
            return false;
        }
        
        // Recursively validate the left and right subtrees with updated min and max values
        return validBST(node.left, min, node.val) && validBST(node.right, node.val, max);

    }

BST Basic Operations

BSTs support three main operations: search, insertion and deletion.

Search

According to the property of BST, for each node:

• return the node if the target value is equal to the value of the node;
• continue searching in the left subtree if the target value is less than the value of the node;
• continue searching in the right subtree if the target value is larger than the value of the node.

    public TreeNode searchBST(TreeNode root, int val) {
        // Base case: If root is null or root's value matches the search value
        if (root == null || root.val == val) {
            return root;
        }
        
        // If the search value is less than the root's value, search in the left subtree
        if (val < root.val) {
            return searchBST(root.left, val);
        }
        // If the search value is greater than the root's value, search in the right subtree
        else {
            return searchBST(root.right, val);
        }
    }

The time complexity of the search operation in a Binary Search Tree (BST) is O(h), where h is the height of the tree. This is because the search operation involves traversing from the root of the tree to the target node along a single path, which is bounded by the height of the tree.

The space complexity of the search operation is also O(h), where h is the height of the tree. This is due to the space required for the recursive calls on the stack during the traversal from the root to the target node. In the worst-case scenario, where the tree is unbalanced and resembles a linked list, the height of the tree is equal to the number of nodes in the tree, resulting in O(n) space complexity. However, in a balanced BST, the height of the tree is logarithmic with respect to the number of nodes, resulting in O(log n) space complexity.

Insertion

We only talk about a typical insertion strategy which minimizes the changes. The main idea is to find out a proper leaf position for the target node and then insert the node as a leaf. Therefore, insertion will begin as a search.

Similar to our search strategy, for each node, we will:

• search the left or right subtrees according to the relation of the value of the node and the value of our target node;
• repeat STEP 1 until reaching an external node;
• add the new node as its left or right child depending on the relation of the value of the node and the value of our target node.

In this way, we add a new node and maintain the property of BST.

Deletion

Our solution is to replace the target node with a proper child. According to the number of its children, we should consider three different cases:

1. If the target node has no child, we can simply remove the node.
2. If the target node has one child, we can use its child to replace itself.
3. If the target node has two children, replace the node with its in-order successor or predecessor node and delete that node.

Height-Balanced BST

A height-balanced tree is a binary tree in which the height difference between the left and right subtrees of any node is at most one. In other words, for every node in the tree, the heights of its left and right subtrees differ by at most one.

Height balance is important in maintaining the efficiency of various tree-based data structures, such as AVL trees and Red-Black trees, which are specifically designed to ensure height balance.

Efficient Operations: Maintaining height balance ensures that the depth of the tree remains relatively small, which in turn ensures efficient tree traversal and search operations. Operations such as insertion, deletion, and search have time complexities of O(log n) in a height-balanced tree, where n is the number of nodes in the tree.

Prevent Degeneration: Height balance prevents the tree from degenerating into a linear structure, which could happen if one subtree becomes significantly deeper than the other. Degeneration can lead to inefficient tree operations, with worst-case time complexities approaching O(n) for operations like search and traversal.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        // Check if the height difference of left and right subtrees is at most one
        if (Math.abs(height(root.left) - height(root.right)) <= 1) {
            // Recursively check if both left and right subtrees are balanced
            return isBalanced(root.left) && isBalanced(root.right);
        }
        
        return false;
    }
    
    // Function to calculate the height of a binary tree
    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        // Recursively calculate the height of left and right subtrees
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        
        // Return the maximum height of the left and right subtrees, plus 1 for the current node
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

Examples:

• BST In order successor
• BST - In Order Iterator
• BST Insertion
• Delete in BST
• Kth-Largest-Element-in-a-Stream-with-bst
• From Sorted Array To Balanced BST