C# - Binary Tree template - solves many BST problems - DFS


  • 0

    There is a template for solving many BST problems here is the basic idea starting with standard In Order Traversal. Pay attention to the "VISIT NODE" block, depending on the problem you will plug in your custom logic into this part of the template.

        public IList<int> InorderTraversal(TreeNode root) 
        {
            IList<int> list = new List<int>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode node = root;
            while (node != null || stack.Count > 0)
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.left;
                }
                else
                {
                    node = stack.Pop();
                    
                    // ---------------------------------------
                    // VISIT NODE BEGIN
                    // ---------------------------------------
                    list.Add(node.val);
                    // ---------------------------------------
                    // VISIT NODE END
                    // ---------------------------------------
                    
                    node = node.right;
                }
            }
            
            return list;
        }
    

    Here we can adapt this to the BST iterator problem where "VISIT NODE" means this is the next value and break here.

    public class BSTIterator {
    
        private TreeNode curr;
        private Stack<TreeNode> stack;
        
        public BSTIterator(TreeNode root) 
        {
            this.curr = root;
            this.stack = new Stack<TreeNode>();
        }
    
        /** @return whether we have a next smallest number */
        public bool HasNext() 
        {
            return this.curr != null || this.stack.Count > 0;
        }
    
        /** @return the next smallest number */
        public int Next() 
        {
            int val = 0;
            while (this.curr != null || this.stack.Count > 0)
            {
                if (curr != null)
                {
                    this.stack.Push(curr);
                    curr = curr.left;
                }
                else
                {
                    this.curr = stack.Pop();
                    
                    // ---------------------------------------
                    // VISIT NODE BEGIN
                    // ---------------------------------------
                    val = curr.val;   
                    // ---------------------------------------
                    // VISIT NODE END
                    // ---------------------------------------
                    
                    this.curr = curr.right;
                    break;
                }
            }
            return val;
        }
    }
    

    Here we adaptt it to find the Kth smallest value

        public int KthSmallest(TreeNode root, int k) 
        {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode curr = root;
            
            while (curr != null || stack.Count > 0)
            {
                if (curr != null)
                {
                    stack.Push(curr);
                    curr = curr.left;
                }
                else
                {
                    curr = stack.Pop();
                    
                    // ---------------------------------------
                    // VISIT NODE BEGIN
                    // ---------------------------------------
                    if (--k == 0) return curr.val;
                    // ---------------------------------------
                    // VISIT NODE END
                    // ---------------------------------------
                    
                    curr = curr.right;
                }
            }
            
            return -1;
        }
    

    Validate Binary Search Tree

        public bool IsValidBST(TreeNode root) 
        {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode curr = root;
            TreeNode prev = null;
            
            while (curr != null || stack.Count > 0)
            {
                if (curr != null)
                {
                    stack.Push(curr);
                    curr = curr.left;
                }
                else
                {
                    curr = stack.Pop();
                    
                    // ---------------------------------------
                    // VISIT NODE BEGIN
                    // ---------------------------------------
                    if (prev != null && prev.val >= curr.val) return false;
                    prev = curr;
                    // ---------------------------------------
                    // VISIT NODE END
                    // ---------------------------------------
                    
                    curr = curr.right;
                }
            }
            
            return true;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.