Skip to main content

Binary Tree Modification

Populate Next Right Pointers in Each Node​

Connect each node to its next right node at the same level. If no next right node exists, set next to null.

Before & After Visualization​

Algorithm: Level-by-Level Traversal​

public void PopulateNextRightPointersInTree(TreeLinkNode root)
{
    TreeLinkNode top = root;
    while (top != null)
    {
        TreeLinkNode curr = top;
        TreeLinkNode prev = null;
        while (curr != null)
        {
            if (curr.left != null)
            {
                if (prev != null)
                {
                    prev.next = curr.left;
                }
                prev = curr.left;
            }
            if (curr.right != null)
            {
                if (prev != null)
                {
                    prev.next = curr.right;
                }
                prev = curr.right;
            }
            curr = curr.next;
        }
        // First try going left, otherwise right. If right is not an option, try top.next
        top = top.left != null?top.left : top.right != null?top.right : top.next;
    }
}

Populate Next Right Pointers in Perfect Binary Tree​

For a perfect binary tree, the algorithm is simpler since every level is complete.

public void PopulateNextRightPointersInPerfectBinaryTree(TreeLinkNode root)
{
    if (root == null) return;
    TreeLinkNode pre = root;
    TreeLinkNode cur = null;
    while (pre.left != null)
    {
        cur = pre;
        while (cur != null)
        {
            cur.left.next = cur.right;
            if (cur.next != null) cur.right.next = cur.next.left;
            cur = cur.next;
        }
        pre = pre.left;
    }
}

Convert Sorted Array to Binary Search Tree​

Build a height-balanced BST from a sorted array using divide-and-conquer.

Visualization​

public TreeNode SortedArrayToBST(int[] nums)
{
    return SortedArrayToBST(nums, 0, nums.Length - 1);
}

public TreeNode SortedArrayToBST(int[] nums, int low, int high)
{
    if (low > high) return null;
    int mid = low + (high - low) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = SortedArrayToBST(nums, low, mid - 1);
    root.right = SortedArrayToBST(nums, mid + 1, high);

    return root;
}

Delete Node in a BST​

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Three Cases for Deletion​

Case 3 Visualization (Two Children)​

public TreeNode DeleteNode(TreeNode root, int key)
{
        
    if(root == null) return root;
    if(key<root.val)
    {
        root.left = DeleteNode(root.left, key);     
    }
    else if(key>root.val)
    {
        root.right = DeleteNode(root.right, key);
    }
    else
    {
        if(root.left == null) return root.right;
        if(root.right == null) return root.left;
        
        var rightSmallest = root.right;
        while(rightSmallest.left != null) rightSmallest = rightSmallest.left;
        rightSmallest.left = root.left;
        return root.right;
    }
    
    return root;
}

Key Insights​

Interview Tips
  • Next pointer problems: O(1) space by using existing next pointers for level traversal
  • Sorted array to BST: Always pick middle element for balanced tree
  • BST deletion: Inorder successor = leftmost node in right subtree
Last updated on