assignment category DSA: Locking tf in - Part 1

#dsa #java #schoolwork
25/12/2024 18 Min.
Written by: Yuk

Binary Tree / Binary Search Tree / AVL Tree

Problem List (40 Problems)

G4G - Check for BST

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

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

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

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

G4G - Tree Boundary Traversal

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

Pretty straight forward i guess.

G4G - Top View of Binary Tree

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

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

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

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

G4G - Diameter of a Binary Tree

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

Global variable maxDiameter to keep track of the max diameter.

G4G - Height of Binary Tree

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

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

G4G - Bottom View of Binary Tree

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

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

G4G - Identical Trees

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

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

G4G - Sum Tree

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

G4G - Level Order in spiral form

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

Just BFS with a boolean flag.

G4G - Minimum element in BST

int minValue(Node root) {
    Node node = root;
    while (node.left != null) {
        node = node.left;
    }
    return node.data;
}

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

G4G - Preorder Traversal

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

Process first, then left and right node.

G4G - In-order Traversal

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

Left first, then process, then right node.

G4G - Postorder Traversal

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

Left, right, then process.

G4G - Count Leaves in Binary Tree

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

G4G - Search a node in BST

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

Follow the properties of BST.

G4G - Size of Binary Tree

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

G4G - Sum of Binary Tree

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

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

G4G - Count Non-Leaf Nodes in Tree

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

G4G - Level order traversal

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

BFS - Breath first search (Breath first traversal).

G4G - Mirror Tree

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

G4G - Right View of Binary Tree

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

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

G4G - Nodes without a Sibling

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

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

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

G4G - Kth largest element in BST

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

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

G4G - Symmetric Tree

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

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

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

The pattern is trippy its not just reversing BFS apparently.

G4G - LCA in BST

G4G - LCA in Binary Tree

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

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

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

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

G4G - Median of BST

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

Can be done with less space.

G4G - Inorder Successor in BST

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

Can be done with less space.

G4G - Root to leaf path sum

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

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

G4G - K distance from root

// 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);
}

G4G - Leaves at Same Level or Not

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

G4G - Array to BST

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

Binary search is the foundation.

G4G - Minimum Depth of a Binary Tree

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

G4G - Binary Tree to BST

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

G4G - Odd even level difference

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