C# - iterative DFS - in order traversal


  • 0

    Given that you will have to visit all nodes in the tree regardless I prefer DFS over BFS as it will require less memory for most cases. And the iterative solution should be an improvement over the recursive.

        public int FindBottomLeftValue(TreeNode root) 
        {
            Stack<int> levelStack = new Stack<int>();
            Stack<TreeNode> nodeStack = new Stack<TreeNode>();
            int level = 0;
            TreeNode curr = root;
            
            int maxLevel = 0;
            int leftValue = root.val;
            
            while (curr != null || nodeStack.Count > 0)
            {
                if (curr != null)
                {
                    nodeStack.Push(curr);
                    levelStack.Push(level);
                    curr = curr.left;
                    level++;
                }
                else
                {
                    curr = nodeStack.Pop();
                    level = levelStack.Pop();
                    
                    // visit
                    if (level > maxLevel)
                    {
                        maxLevel = level;
                        leftValue = curr.val;
                    }
                    
                    curr = curr.right;
                    level++;
                }
            }
            
            return leftValue;
        }
    

Log in to reply
 

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