DSA: Locking tf in - Part 1

#dsa #java #schoolwork
Dec. 25th 2024 18 Min.
Locking in for some DSA finals idk (40 Problems)
Written by: Yuk

Binary Tree / Binary Search Tree / AVL Tree

Problem List (40 Problems)

Block

G4G - Check for BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
boolean isBST(Node root) {
    return isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

boolean isBSTUtil(Node node, int min, int max) {
    if (node == null) {
        return true;
    }
    if (node.data < min || node.data > max) {
        return false;
    }
    return isBSTUtil(node.left, min, node.data - 1) &&
        isBSTUtil(node.right, node.data + 1, max);
}
Java

Levering the characteristics of BST to narrow down the range of each nodes, immediately return false if condition is not met.

G4G - Left View of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ArrayList<Integer> leftView(Node root) {
    ArrayList<Integer> leftView = new ArrayList<>();

    if (root == null) {
        return leftView;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        int n = queue.size();

        for (int i = 1; i <= n; i++) {
            Node node = queue.poll();
            if (i == 1) {
                leftView.add(node.data);
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }
    return leftView;
}
Java

Basically perform a BFS, it will always guaranteed the left most node at each level.

G4G - Tree Boundary Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
private void leftBoundary(Node node, ArrayList<Integer> boundPath) {
    while (node != null) {
        if (node.left != null || node.right != null) {
            boundPath.add(node.data);
        }
        if (node.left != null) {
            node = node.left;
        } else {
            node = node.right;
        }
    }
}

private void leafNodes(Node node, ArrayList<Integer> boundPath) {
    if (node == null) {
        return;
    }
    if (node.left == null && node.right == null) {
        boundPath.add(node.data);
        return;
    }
    leafNodes(node.left, boundPath);
    leafNodes(node.right, boundPath);
}

private void rightBoundary(Node node, ArrayList<Integer> boundPath) {
    ArrayList<Integer> temp = new ArrayList<>();
    while (node != null) {
        if (node.left != null || node.right != null) {
            temp.add(node.data);
        }
        if (node.right != null) {
            node = node.right;
        } else {
            node = node.left;
        }
    }
    for (int i = temp.size() - 1; i >= 0; i--) {
        boundPath.add(temp.get(i));
    }
}

ArrayList<Integer> boundaryTraversal(Node root) {
    ArrayList<Integer> boundPath = new ArrayList<>();

    if (root == null) {
        return boundPath;
    }

    boundPath.add(root.data);

    if (root.left == null && root.right == null) return boundPath;
    if (root.left != null) {
        leftBoundary(root.left, boundPath);
    }
    leafNodes(root, boundPath);
    if (root.right != null) {
        rightBoundary(root.right, boundPath);
    }
    return boundPath;
}
Java

Pretty straight forward i guess.

G4G - Top View of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
static ArrayList<Integer> topView(Node root) {
    ArrayList<Integer> topView = new ArrayList<>();

    if (root == null) {
        return topView;
    }

    Map<Integer, Integer> hdMap = new TreeMap<>();
    Queue<Pair> queue = new LinkedList<>();
    queue.add(new Pair(root, 0));

    while (!queue.isEmpty()) {
        Pair pair = queue.poll();
        Node node = pair.node;
        int hd = pair.hd;

        if (!hdMap.containsKey(hd)) {
            hdMap.put(hd, node.data);
        }

        if (node.left != null) {
            queue.add(new Pair(node.left, hd - 1));
        }
        if (node.right != null) {
            queue.add(new Pair(node.right, hd + 1));
        }
    }

    topView.addAll(hdMap.values());

    return topView;
}

static class Pair {
    Node node;
    int hd;

    Pair(Node node, int hd) {
        this.node = node;
        this.hd = hd;
    }
}
Java

Quite damn convoluted but basically we introduce horizontal distance as hd, root have hd = 0 and each node to the left / right will -1 / +1. We associate each node to their hd with the Pair object. Perform BFS and adding the node to a map with hd as key will allow us to find the first occurrence of the node with the unique hd. BFS guaranteed that once finish then all of the node inside that map will be our top view.

G4G - Balanced Tree Check

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean isBalanced(Node root) {
    return checkHeight(root) != -1;
}

private int checkHeight(Node node) {
    if (node == null) {
        return 0;
    }

    int leftHeight = checkHeight(node.left);
    int rightHeight = checkHeight(node.right);

    if (leftHeight == -1 || rightHeight == -1) {
        return -1;
    }

    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    }

    return Math.max(leftHeight, rightHeight) + 1;
}
Java

This approach is more efficient with O(n)O(n) time (one pass), rather than explicitly finding exact heights and calculating balance factor like in AVL tree which is O(n2)O(n^2) (two pass).

G4G - Diameter of a Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxDiameter = 0;
    
int diameter(Node root) {
    calculateHeight(root);
    return maxDiameter;
}

private int calculateHeight(Node node) {
    if (node == null) {
        return 0;
    }

    int leftHeight = calculateHeight(node.left);
    int rightHeight = calculateHeight(node.right);
    maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
    
    return Math.max(leftHeight, rightHeight) + 1;
}
Java

Global variable maxDiameter to keep track of the max diameter.

G4G - Height of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// What is expected:
int height(Node root) {
    if (root == null) {
        return 0;
    }

    int leftHeight = height(root.left);
    int rightHeight = height(root.right);

    return Math.max(leftHeight, rightHeight) + 1;
}

// What worked:
int height = 0;
    
int height(Node root) {
    calculateHeight(root);
    return height;
}

private int calculateHeight(Node node) {
    if (node == null) {
        return 0;
    }

    int leftHeight = calculateHeight(node.left);
    int rightHeight = calculateHeight(node.right);
    height = Math.max(leftHeight, rightHeight);
    
    return Math.max(leftHeight, rightHeight) + 1;
}
Java

Global variable height to keep track of the max height. Not really sure why the first one failed.

G4G - Bottom View of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
static ArrayList<Integer> bottomView(Node root) {
    ArrayList<Integer> bottomView = new ArrayList<>();

    if (root == null) {
        return bottomView;
    }

    Map<Integer, Integer> hdMap = new TreeMap<>();
    Queue<Pair> queue = new LinkedList<>();
    queue.add(new Pair(root, 0));

    while (!queue.isEmpty()) {
        Pair pair = queue.poll();
        Node node = pair.node;
        int hd = pair.hd;

        hdMap.put(hd, node.data);

        if (node.left != null) {
            queue.add(new Pair(node.left, hd - 1));
        }
        if (node.right != null) {
            queue.add(new Pair(node.right, hd + 1));
        }
    }

    bottomView.addAll(hdMap.values());

    return bottomView;
}

static class Pair {
    Node node;
    int hd;

    Pair(Node node, int hd) {
        this.node = node;
        this.hd = hd;
    }
}
Java

Exactly like G4G - Top View of Binary Tree but always update the map.

G4G - Identical Trees

1
2
3
4
5
6
7
8
9
10
11
boolean isIdentical(Node r1, Node r2) {
    if (r1 == null && r2 == null) {
        return true;
    }

    if (r1 == null || r2 == null || r1.data != r2.data) {
        return false;
    }

    return isIdentical(r1.left, r2.left) && isIdentical(r1.right, r2.right);
}
Java

Any kind of traversal works (O(n)O(n)).

G4G - Sum Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
boolean isSumTree(Node root) {
    if (root == null || (root.left == null && root.right == null)) {
        return true;
    }

    int leftSum = sum(root.left);
    int rightSum = sum(root.right);

    if (root.data == leftSum + rightSum && isSumTree(root.left) && isSumTree(root.right)) {
        return true;
    }

    return false;
}

int sum(Node root) {
    if (root == null) {
        return 0;
    }

    return root.data + sum(root.left) + sum(root.right);
}
Java

G4G - Level Order in spiral form

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
ArrayList<Integer> findSpiral(Node root) {
    ArrayList<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);

    boolean leftToRight = true;

    while (!queue.isEmpty()) {
        int size = queue.size();
        ArrayList<Integer> currentLevel = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            Node currentNode = queue.poll();
            currentLevel.add(currentNode.data);

            if (currentNode.left != null) {
                queue.offer(currentNode.left);
            }

            if (currentNode.right != null) {
                queue.offer(currentNode.right);
            }
        }

        if (leftToRight) {
            Collections.reverse(currentLevel);
        }

        result.addAll(currentLevel);
        leftToRight = !leftToRight;
    }

    return result;
}
Java

Just BFS with a boolean flag.

G4G - Minimum element in BST

1
2
3
4
5
6
7
int minValue(Node root) {
    Node node = root;
    while (node.left != null) {
        node = node.left;
    }
    return node.data;
}
Java

Minimum data in a BST will always be at the left-most node.

G4G - Preorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static ArrayList<Integer> preorder(Node root) {
    ArrayList<Integer> results = new ArrayList<>();
    preorderHelper(root, results);
    return results;
}

static void preorderHelper(Node root, ArrayList<Integer> results) {
    if (root == null) {
        return;
    }

    results.add(root.data);
    preorderHelper(root.left, results);
    preorderHelper(root.right, results);
}
Java

Process first, then left and right node.

G4G - In-order Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static ArrayList<Integer> inOrder(Node root) {
    ArrayList<Integer> results = new ArrayList<>();
    inOrderHelper(root, results);
    return results;
}

static void inOrderHelper(Node root, ArrayList<Integer> results) {
    if (root == null) {
        return;
    }

    inOrderHelper(root.left, results);
    results.add(root.data);
    inOrderHelper(root.right, results);
}
Java

Left first, then process, then right node.

G4G - Postorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static ArrayList<Integer> postOrder(Node root) {
    ArrayList<Integer> results = new ArrayList<>();
    postOrderHelper(root, results);
    return results;
}

static void postOrderHelper(Node root, ArrayList<Integer> results) {
    if (root == null) {
        return;
    }

    postOrderHelper(root.left, results);
    postOrderHelper(root.right, results);
    results.add(root.data);
}
Java

Left, right, then process.

G4G - Count Leaves in Binary Tree

1
2
3
4
5
6
7
8
9
10
11
int countLeaves(Node node) {
    if (node == null) {
        return 0;
    }

    if (node.left == null && node.right == null) {
        return 1;
    }

    return countLeaves(node.left) + countLeaves(node.right);
}
Java

G4G - Search a node in BST

1
2
3
4
5
6
7
8
9
10
11
boolean search(Node root, int x) {
    if (x == root.data) {
        return true;
    } else if (x < root.data && root.left != null) {
        return search(root.left, x);
    } else if (x > root.data && root.right != null) {
        return search(root.right, x);
    } else {
        return false;
    }
}
Java

Follow the properties of BST.

G4G - Size of Binary Tree

1
2
3
4
public static int getSize(Node node) {
    if (node == null) return 0;
    return getSize(node.left) + getSize(node.right) + 1;
}
Java

G4G - Sum of Binary Tree

1
2
3
4
5
6
7
static int sumBT(Node root) {
    if (root == null) {
        return 0;
    }

    return root.data + sumBT(root.left) + sumBT(root.right);
}
Java

G4G - Count Non-Leaf Nodes in Tree

1
2
3
4
5
int countNonLeafNodes(Node root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 0;
    return countNonLeafNodes(root.left) + countNonLeafNodes(root.right) + 1;
}
Java

G4G - Level order traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static ArrayList<Integer> levelOrder(Node root) {
    ArrayList<Integer> bfs = new ArrayList<>();
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        Node current = queue.poll();
        bfs.add(current.data);
        
        if (current.left != null) queue.offer(current.left);
        if (current.right != null) queue.offer(current.right);
    }

    return bfs;
}
Java

BFS - Breath first search (Breath first traversal).

G4G - Mirror Tree

1
2
3
4
5
6
7
8
9
10
11
12
void mirror(Node node) {
    if (node == null) {
        return;
    }

    Node temp = node.left;
    node.left = node.right;
    node.right = temp;

    mirror(node.left);
    mirror(node.right);
}
Java

G4G - Right View of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ArrayList<Integer> rightView(Node root) {
    ArrayList<Integer> rightView = new ArrayList<>();

    if (root == null) {
        return rightView;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        int n = queue.size();

        for (int i = 1; i <= n; i++) {
            Node node = queue.poll();
            if (i == n) {
                rightView.add(node.data);
            }
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }
    return rightView;
}
Java

Exactly like G4G - Left View of Binary Tree but add the last one in the BFS traversal.

G4G - Nodes without a Sibling

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
ArrayList<Integer> noSibling(Node root) {
    ArrayList<Integer> onlyChild = new ArrayList<>();
    
    if (root == null) {
        return onlyChild;
    }
    
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        
        if (node.left != null && node.right == null) {
            onlyChild.add(node.left.data);
        }
        if (node.right != null && node.left == null) {
            onlyChild.add(node.right.data);
        }
        
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    
    if (onlyChild.isEmpty()) {
        onlyChild.add(-1);
    }
    
    onlyChild.sort(Comparator.comparing(Integer::valueOf));
    
    return onlyChild;
}
Java

The definition threw me off quite badly but onlyChild are those that doesn’t share any parents with the other node at it’s same level.

G4G - Insert a node in a BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node insert(Node root, int Key) {
    if (root == null) {
        root = new Node(Key);
        return root;
    }
        
    if (Key < root.data) {
        root.left = insert(root.left, Key);
    } else if (Key > root.data) {
        root.right = insert(root.right, Key);
    }
        
    return root;
}
Java

G4G - Kth largest element in BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int kthLargest(Node root, int k) {
    int[] count = new int[1];
    int[] result = new int[1];
    
    reverseInOrderTraversal(root, k, count, result);
    
    return result[0];
}

private void reverseInOrderTraversal(Node node, int k, int[] count, int[] result) {
    if (node == null || count[0] >= k) {
        return;
    }
    
    reverseInOrderTraversal(node.right, k, count, result);
    
    count[0]++;
    
    if (count[0] == k) {
        result[0] = node.data;
        return;
    }
    
    reverseInOrderTraversal(node.left, k, count, result);
}
Java

Traverse in reverse in-order (right -> process -> left) and helper variables to keep track of the k-th node.

G4G - Symmetric Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static boolean isSymmetric(Node root) {
    if (root == null) {
        return true;
    }

    return isMirror(root.left, root.right);
}

private static boolean isMirror(Node left, Node right) {
    if (left == null && right == null) {
        return true;
    }

    if (left == null || right == null) {
        return false;
    }

    return (left.data == right.data) 
           && isMirror(left.left, right.right) 
           && isMirror(left.right, right.left);
}
Java

Some recursive magic idk. I think basically the key is that its checking both subtree of the root at the same time.

G4G - Reverse Level Order Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ArrayList<Integer> reverseLevelOrder(Node root) {
    LinkedList<Integer> rbfs = new LinkedList<>();
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        Node current = queue.poll();
        rbfs.addFirst(current.data);
        
        if (current.right != null) queue.offer(current.right);
        if (current.left != null) queue.offer(current.left);
    }

    return new ArrayList<>(rbfs);
}
Java

The pattern is trippy its not just reversing BFS apparently.

G4G - LCA in BST

G4G - LCA in Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public Node LCA(Node root, int n1, int n2) {
    if (root == null) {
        return null;
    }

    if (root.data == n1 || root.data == n2) {
        return root;
    }

    Node leftLCA = LCA(root.left, n1, n2);
    Node rightLCA = LCA(root.right, n1, n2);

    if (leftLCA != null && rightLCA != null) {
        return root;
    }

    return (leftLCA != null) ? leftLCA : rightLCA;
}
Java

LCA (Least Common Ancestor), basically if n1 and n2 can be found in both left and right subtree then LCA is the current root, if n1 and n2 is both in a subtree then LCA is also in that subtree. There will always be a LCA given n1 and n2 do exist in the tree.

G4G - Maximum Width of Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int getMaxWidth(Node root) {
    if (root == null) {
        return 0;
    }
    
    int maxWidth = 1;

    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        int n = queue.size();
        
        if (n > maxWidth) maxWidth = n;

        for (int i = 1; i <= n; i++) {
            Node node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }
    return maxWidth;
}
Java

Modify BFS a bit and width is the number of nodes in the queue after each level.

G4G - Median of BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static float findMedian(Node root) {
    ArrayList<Integer> list = new ArrayList<>();
    inOrder(root, list);
    
    if (list.size() % 2 == 0) {
        return (float) (list.get(list.size() / 2 - 1) + list.get(list.size() / 2)) / 2;
    } else {
        return (float) list.get(list.size() / 2);
    }
}

public static void inOrder(Node node, ArrayList<Integer> list) {
    if (node == null) return;
    
    inOrder(node.left, list);
    list.add(node.data);
    inOrder(node.right, list);
}
Java

Can be done with less space.

G4G - Inorder Successor in BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int inorderSuccessor(Node root, Node x) {
    ArrayList<Integer> list = new ArrayList<>();
    inOrder(root, list);
    
    int successor = -1;
    
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) == x.data && i + 1 < list.size())
            successor = list.get(i + 1);
    }
    
    return successor;
}
    
public static void inOrder(Node node, ArrayList<Integer> list) {
    if (node == null) return;
    
    inOrder(node.left, list);
    list.add(node.data);
    inOrder(node.right, list);
}
Java

Can be done with less space.

G4G - Root to leaf path sum

1
2
3
4
5
6
7
8
9
10
11
12
boolean hasPathSum(Node root, int target) {
    if (root == null) {
        return false;
    }

    if (root.left == null && root.right == null) {
        return target == root.data;
    }

    int remainingTarget = target - root.data;
    return hasPathSum(root.left, remainingTarget) || hasPathSum(root.right, remainingTarget);
}
Java

Basically DFS with a variable to track the remaining sum target.

G4G - K distance from root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// BFS approach:
ArrayList<Integer> Kdistance(Node root, int k) {
    ArrayList<Integer> result = new ArrayList<>();

    if (root == null) {
        return result;
    }

    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    int level = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();

        if (level == k) {
            for (int i = 0; i < size; i++) {
                Node current = queue.poll();
                result.add(current.data);
            }
            break;
        }

        for (int i = 0; i < size; i++) {
            Node current = queue.poll();
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }

        level++;
    }

    return result;
}

// DFS approach:
ArrayList<Integer> Kdistance(Node root, int k) {
    ArrayList<Integer> result = new ArrayList<>();
    dfs(root, k, 0, result);
    return result;
}

void dfs(Node node, int k, int currentDistance, ArrayList<Integer> result) {
    if (node == null) return;

    if (currentDistance == k) {
        result.add(node.data);
        return;
    }

    dfs(node.left, k, currentDistance + 1, result);
    dfs(node.right, k, currentDistance + 1, result);
}
Java

G4G - Leaves at Same Level or Not

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// BFS approach:
boolean check(Node root) {
    if (root == null) {
        return true;
    }

    Queue<Pair> queue = new LinkedList<>();
    queue.add(new Pair(root, 0));
    Integer leafLevel = null;

    while (!queue.isEmpty()) {
        Pair current = queue.poll();
        Node node = current.node;
        int level = current.height;

        if (node.left == null && node.right == null) {
            if (leafLevel == null) {
                leafLevel = level;
            } else if (leafLevel != level) {
                return false;
            }
        }

        if (node.left != null) {
            queue.add(new Pair(node.left, level + 1));
        }
        if (node.right != null) {
            queue.add(new Pair(node.right, level + 1));
        }
    }

    return true;
}

static class Pair {
    Node node;
    int height; 

    Pair(Node node, int height) { 
        this.node = node;
        this.height = height; 
    }
}
Java

G4G - Array to BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public Node sortedArrayToBST(int[] nums) {
    if (nums == null || nums.length == 0) {
        return null;
    }
    return buildBST(nums, 0, nums.length - 1);
}

private Node buildBST(int[] nums, int start, int end) {
    if (start > end) {
        return null;
    }

    int mid = start + (end - start) / 2;
    Node root = new Node(nums[mid]);

    root.left = buildBST(nums, start, mid - 1);
    root.right = buildBST(nums, mid + 1, end);

    return root;
}
Java

Binary search is the foundation.

G4G - Minimum Depth of a Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int minDepth(Node root) {
    if (root == null) {
        return 0;
    }

    Queue<Pair> queue = new LinkedList<>();
    queue.add(new Pair(root, 1));

    while (!queue.isEmpty()) {
        Pair current = queue.poll();
        Node node = current.node;
        int depth = current.depth;

        if (node.left == null && node.right == null) {
            return depth;
        }

        if (node.left != null) {
            queue.add(new Pair(node.left, depth + 1));
        }
        if (node.right != null) {
            queue.add(new Pair(node.right, depth + 1));
        }
    }

    return 0;
}

static class Pair {
    Node node;
    int depth;

    Pair(Node node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}
Java

G4G - Binary Tree to BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Node binaryTreeToBST(Node root) {
    // Step 1: Collect all values from the binary tree.
    ArrayList<Integer> values = new ArrayList<>();
    collectValues(root, values);

    // Step 2: Sort the values.
    Collections.sort(values);

    // Step 3: Build a BST from sorted values.
    return buildBST(values, 0, values.size() - 1);
}

void collectValues(Node node, ArrayList<Integer> values) {
    if (node == null) return;

    collectValues(node.left, values);
    values.add(node.data);
    collectValues(node.right, values);
}

Node buildBST(ArrayList<Integer> values, int start, int end) {
    if (start > end) return null;

    int mid = (start + end) / 2;
    Node root = new Node(values.get(mid));
    root.left = buildBST(values, start, mid - 1);
    root.right = buildBST(values, mid + 1, end);

    return root;
}
Java

G4G - Odd even level difference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int getLevelDiff(Node root) {
    if (root == null) return 0;

    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    boolean isOddLevel = true;
    int oddSum = 0, evenSum = 0;

    while (!queue.isEmpty()) {
        int levelSize = queue.size();

        for (int i = 0; i < levelSize; i++) {
            Node node = queue.poll();

            if (isOddLevel) {
                oddSum += node.data;
            } else {
                evenSum += node.data;
            }

            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }

        isOddLevel = !isOddLevel;
    }

    return oddSum - evenSum;
}
Java