Leetcode: Find-bottom-left-tree-value

Question

https://leetcode.com/problems/find-bottom-left-tree-value/

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1: Input:

 2 / \ 1 3 

Output: 1 Example 2: Input:

 1 / \ 2 3 / / \ 4 5 6 / 7 

Output: 7 Note: You may assume the tree (i.e., the given root node) is not NULL.

Please review for performance. Thanks

using System; using System.Collections.Generic; using Microsoft.VisualStudio.TestTools.UnitTesting; namespace GraphsQuestions { /// <summary> /// https://leetcode.com/problems/find-bottom-left-tree-value/ /// </summary> [TestClass] public class FindBottomLeftTreeValue { //Input: // 2 // / \ // 1 3 [TestMethod] public void SmallTreeTest() { TreeNode root = new TreeNode(2); root.left = new TreeNode(1); root.right = new TreeNode(3); Assert.AreEqual(1, FindBottomLeftValue(root)); } //Input: // 1 // / \ // 2 3 // / / \ // 4 5 6 // / // 7 [TestMethod] public void BigTreeTest() { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.left.left = new TreeNode(4); root.right = new TreeNode(3); root.right.left = new TreeNode(5); root.right.right = new TreeNode(6); root.right.left.left = new TreeNode(7); Assert.AreEqual(7, FindBottomLeftValue(root)); } public int FindBottomLeftValue(TreeNode root) { if (root == null) { throw new NullReferenceException("root is empty"); } Queue<TreeNode> Q = new Queue<TreeNode>(); Q.Enqueue(root); int left = root.val; while (Q.Count > 0) { // we always push the left node first then we peek, so the first item is the most left //for the entire level of the tree int qSize = Q.Count; left = Q.Peek().val; for (int i = 0; i < qSize; i++) { var current = Q.Dequeue(); if (current.left != null) { Q.Enqueue(current.left); } if (current.right != null) { Q.Enqueue(current.right); } } } return left; } } /* Definition for a binary tree node.*/ public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } } 

Answer 1

Please review for performance.

The performance looks fine to me. Some key observations:

• It's clear that all nodes must be visited to compute the correct answer, so the solution cannot be better than \$O(n)\$ time.
• Traversing in level order as you did will require as much additional space as the number of nodes on the most dense level.
• Traversing depth first would require as much additional space as the longest path from root to leaf.

Without knowing in advance the shape of the tree (whether it's deep or wide), and given TreeNode as defined and no additional helper data structures, it's not possible to tell whether DFS or BFS is better. So they are both equally fine, as neither uses space excessively.