Skip to main content

Simply Traverse

Simply DFS​

Sum of Binary Tree​

Basic·

Calculate the sum of all node values in a binary tree by traversing each node and adding its value to the total sum.

3 Approachesclick to switch
FIG. SUM OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once.
Space
O(h)
  • The recursion call stack grows with the tree's height h.
def sumBT(self, root):
def dfs(node):
if not node:
return 0
return node.data + dfs(node.left) + dfs(node.right)
 
return dfs(root)

Size of Binary Tree​

Basic·

Count the total number of nodes in a binary tree. Each node contributes 1 to the count, regardless of its value.

3 Approachesclick to switch
FIG. SIZE OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs is called once per node, n being the total node count.
Space
O(h)
  • The recursion stack depth equals the tree height h.
def getSize(self, root: Optional["Node"]) -> int:
def dfs(node):
if not node:
return 0
return 1 + dfs(node.left) + dfs(node.right)
 
return dfs(root)

Count Leaves in Binary Tree​

Basic·

Count leaf nodes (nodes with no children) in a binary tree. A leaf node has both left and right children as null.

3 Approachesclick to switch
FIG. COUNT LEAVES IN BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n is the number of nodes - dfs visits every node exactly once.
Space
O(h)
  • h is the tree height - the recursion stack in dfs grows one frame per level.
def countLeaves(self, root):
def dfs(node):
if not node:
return 0
if not node.left and not node.right:
return 1
return dfs(node.left) + dfs(node.right)
 
return dfs(root)

Count Non-Leaf Nodes in Tree​

Basic·

Count internal nodes (non-leaf nodes) in a binary tree. A non-leaf node has at least one child (left or right).

3 Approachesclick to switch
FIG. COUNT NON LEAF NODES IN TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once, summing 1 for every node with at least one child.
Space
O(h)
  • The recursion stack goes one frame deep per level, up to the tree height h.
def countNonLeafNodes(self, root):
def dfs(node):
if not node:
return 0
if not node.left and not node.right:
return 0
return 1 + dfs(node.left) + dfs(node.right)
 
return dfs(root)

Sum of Leaf Nodes​

Easy·

Calculate the sum of all leaf node values in a binary tree. A leaf node has no children (both left and right are null).

3 Approachesclick to switch
FIG. SUM OF LEAF NODES● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n is the number of nodes - dfs visits every node exactly once.
Space
O(h)
  • h is the tree height - the recursion stack in dfs grows one frame per level.
def leafSum(self, root):
def dfs(node):
if not node:
return 0
if not node.left and not node.right:
return node.data
return dfs(node.left) + dfs(node.right)
 
return dfs(root)

Max and min element in Binary Tree​

Easy·

Find the maximum and minimum values among all nodes in a binary tree by comparing each node's value during traversal.

3 Approachesclick to switch
FIG. MAX AND MIN ELEMENT IN BINARY TREE RECURSIVE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits every node exactly once, called twice (once for findMax, once for findMin), so it's 2n collapsed to O(n).
Space
O(h)
  • The recursion call stack grows to the tree's height h.
def findMax(self, root):
def dfs(node):
if not node:
return -float("inf")
return max(node.data, dfs(node.left), dfs(node.right))
 
return dfs(root)
 
 
def findMin(self, root):
def dfs(node):
if not node:
return float("inf")
return min(node.data, dfs(node.left), dfs(node.right))
 
return dfs(root)

Vertical Width of a Binary Tree​

Medium·

Find the vertical width of a binary tree. The vertical width is the number of vertical columns needed to display the tree, where each node is assigned a column based on its horizontal distance from the root.

3 Approachesclick to switch
FIG. VERTICAL WIDTH OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once, updating mini/maxi at each.
Space
O(h)
  • The recursion stack goes one frame deep per level, up to the tree height h.
def verticalWidth(self, root):
def dfs(node, col):
nonlocal mini, maxi
if not node:
return
mini, maxi = min(mini, col), max(maxi, col)
dfs(node.left, col - 1)
dfs(node.right, col + 1)
 
mini, maxi = float("inf"), -float("inf")
dfs(root, 0)
return maxi - mini + 1 if mini != float("inf") else 0

1469. Find All The Lonely Nodes​

Easy·

A lonely node is a node that is the only child of its parent node. Find all lonely nodes in a binary tree. The root node is never lonely as it has no parent.

3 Approachesclick to switch
FIG. FIND ALL THE LONELY NODES● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once, doing constant work per call.
Space
O(h)
  • The recursion call stack grows one frame per level, up to the tree height h.
def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:
def dfs(node):
if not node:
return
if not node.left and node.right:
lonely.append(node.right.val)
if node.left and not node.right:
lonely.append(node.left.val)
dfs(node.left)
dfs(node.right)
 
lonely = []
dfs(root)
return lonely

965. Univalued Binary Tree​

Easy·

A binary tree is univalued if every node in the tree has the same value. Check if a given binary tree is univalued.

3 Approachesclick to switch
FIG. UNIVALUED BINARY TREE RECURSIVE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once.
Space
O(h)
  • The recursion stack holds one frame per level on the current path, where h is the tree height.
def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
def dfs(node):
if not node:
return True
left_result = dfs(node.left)
right_result = dfs(node.right)
return left_result and right_result and root.val == node.val
 
return dfs(root)

404. Sum of Left Leaves​

Easy·

Given the root of a binary tree, return the sum of all left leaves. A left leaf is a leaf which is the left child of another node.

3 Approachesclick to switch
FIG. SUM OF LEFT LEAVES● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each node exactly once.
Space
O(h)
  • The recursion call stack grows with tree height h.
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return 0
total = node.left.val if is_leaf(node.left) else 0
total += dfs(node.left)
total += dfs(node.right)
return total
 
is_leaf = lambda node: node and not node.left and not node.right
 
return dfs(root)

1315. Sum of Nodes with Even-Valued Grandparent​

Medium·

Given the root of a binary tree, return the sum of values of nodes with even-valued grandparent. A grandparent is the parent of a parent of a node.

3 Approachesclick to switch
FIG. SUM OF NODES WITH EVEN VALUED GRANDPAREN● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • dfs visits each of the n nodes exactly once, doing constant work per call.
Space
O(h)
  • The recursion call stack grows one frame per level, so it never exceeds the tree's height h.
def sumEvenGrandparent(self, root: Optional[TreeNode]) -> int:
def dfs(node, parent, gparent):
if not node:
return 0
left_result = dfs(node.left, node.val, parent)
right_result = dfs(node.right, node.val, parent)
current = node.val if gparent % 2 == 0 else 0
return current + left_result + right_result
 
return dfs(root, -1, -1)

671. Second Minimum Node In a Binary Tree​

Easy·
3 Approachesclick to switch
FIG. SECOND MINIMUM NODE IN A BINARY TREE RECURSIVE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • rec visits each of the n nodes exactly once.
Space
O(h)
  • The recursion call stack grows with the tree's height h.
def findSecondMinimumValue(self, root: Optional[TreeNode]) -> int:
def rec(node):
nonlocal mini
if not node:
return -1
if node.val != root.val:
mini = min(mini, node.val)
rec(node.left) if node.left else None
rec(node.right) if node.right else None
 
mini = float("inf")
rec(root)
return mini if mini != float("inf") else -1

Simply BFS​

637. Average of Levels in Binary Tree​

Easy·

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array.

3 Approachesclick to switch
FIG. 637 AVERAGE OF LEVELS● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Each of the n nodes is popped from queue and processed exactly once.
Space
O(w)
  • queue holds at most one full level, bounded by the tree's max width w.
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
queue = collections.deque([root])
levels = []
while queue:
total = count = 0
for _ in range(len(queue)):
node = queue.popleft()
if node:
total += node.val
count += 1
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
if count:
levels.append(total / count)
return levels

1302. Deepest Leaves Sum​

Medium·

Given the root of a binary tree, return the sum of values of its deepest leaves.

3 Approachesclick to switch
FIG. DEEPEST LEAVES SUM● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Each node is popped from queue and processed exactly once.
Space
O(w)
  • queue holds one complete level at a time, so it grows to w, the tree's maximum width.
def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
queue = collections.deque([root])
total = 0
while queue:
total = 0
for _ in range(len(queue)):
node = queue.popleft()
if node:
if not node.left and not node.right:
total += node.val
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
return total

1161. Maximum Level Sum of a Binary Tree​

Medium·

Given the root of a binary tree, return the number of the level that has the maximum sum (1-indexed).

3 Approachesclick to switch
FIG. MAXIMUM LEVEL SUM OF BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Each of the n nodes is popped from queue and its value added into total exactly once.
Space
O(w)
  • queue holds one complete level at a time, bounded by the tree's maximum width w.
def maxLevelSum(self, root: Optional[TreeNode]) -> int:
queue = collections.deque([root])
level = maxi_level = 1
maxi = -float("inf")
while queue:
total = 0
for _ in range(len(queue)):
node = queue.popleft()
if node:
total += node.val
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
if maxi < total:
maxi = total
maxi_level = level
level += 1
return maxi_level

Max Level Sum in Binary Tree​

Easy·

Find the level in a binary tree that has the maximum sum of node values. Return the maximum sum found across all levels.

3 Approachesclick to switch
FIG. MAX LEVEL SUM IN BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Every node is enqueued and dequeued exactly once while accumulating each level's total.
Space
O(w)
  • queue holds all nodes of one level at a time, so it never exceeds the tree's maximum width w.
def maxLevelSum(self, root):
queue = collections.deque([root])
maxi = -float("inf")
while queue:
total = None
for _ in range(len(queue)):
node = queue.popleft()
if node:
total = node.data + (total if total else 0)
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
if total:
maxi = max(maxi, total)
return maxi

Largest value in each level​

Easy·

Find the largest value in each level of a binary tree and return them as a list.

3 Approachesclick to switch
FIG. LARGEST VALUE IN EACH LEVEL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Each node is popped off queue and visited exactly once.
Space
O(w)
  • queue holds one complete level at a time, bounded by the tree's max width w.
def largestValues(self, root):
queue = collections.deque([root])
result = []
while queue:
maxi = -float("inf")
for _ in range(len(queue)):
node = queue.popleft()
if node:
maxi = max(maxi, node.data)
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
if maxi != -float("inf"):
result.append(maxi)
return result

Sum of Leaf Nodes at Min Level​

Easy·

Find the minimum level where leaf nodes exist, then sum all leaf node values at that specific level. A leaf node has no left or right children.

3 Approachesclick to switch
FIG. SUM OF LEAF NODES AT MIN LEVEL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Each of the n nodes is popped from queue and processed exactly once, level by level.
Space
O(w)
  • queue holds one full level at a time, where w is the tree's maximum width.
def minLeafSum(self, root):
queue = collections.deque([root])
total = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
if not node.left and not node.right:
total += node.data
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
if total != 0:
return total
return 0

Odd even level difference​

Easy·

Calculate the sum of all nodes at odd-numbered levels (1, 3, 5, ...) and subtract the sum of all nodes at even-numbered levels (2, 4, 6, ...). Root is at level 1 (odd level).

3 Approachesclick to switch
FIG. ODD EVEN LEVEL DIFFERENCE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • The while queue loop dequeues every node exactly once via queue.popleft(), so total work across all levels is O(n), where n is the number of nodes.
Space
O(w)
  • queue holds at most one full level's worth of nodes - up to w nodes, where w is the tree's max width.
def getLevelDiff(self, root):
queue = collections.deque([root])
odd = even = 0
is_odd = True
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
if is_odd:
odd += node.data
else:
even += node.data
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
is_odd = not is_odd
return odd - even

Maximum Width of Tree​

Easy·

Find the maximum number of nodes present at any level in a binary tree. The width of a level is the total number of nodes (including null nodes) at that level.

3 Approachesclick to switch
FIG. MAXIMUM WIDTH OF TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Every node is popped from queue and counted exactly once across all n nodes.
Space
O(w)
  • queue holds one full level at a time, so it grows to w, the tree's maximum width.
def maxWidth(self, root):
queue = collections.deque([root])
max_width = 0
while queue:
width = 0
for _ in range(len(queue)):
node = queue.popleft()
if node:
width += 1
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
max_width = max(max_width, width)
return max_width

Maximum Node Level​

Easy·

Find the level in a binary tree that has the maximum number of nodes. Return the level number (0-indexed from root).

3 Approachesclick to switch
FIG. MAXIMUM NODE LEVEL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Each of the n nodes is popped from queue exactly once while summing length per level.
Space
O(w)
  • queue holds one complete level at a time, up to the tree's maximum width w.
def maxNodeLevel(self, root):
queue = collections.deque([root])
level = max_level = max_level_length = 0
while queue:
length = 0
for _ in range(len(queue)):
node = queue.popleft()
if node:
length += 1
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
if max_level_length < length:
max_level_length = length
max_level = level
level += 1
return max_level

Level of a Node in Binary Tree​

Easy·

Find the level of a given node in a binary tree. Return the level (1-indexed from root) if the node exists, otherwise return 0.

3 Approachesclick to switch
FIG. LEVEL OF A NODE IN BINARY TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • queue visits each of the n nodes once, level by level, until target is found (worst case all n).
Space
O(w)
  • queue holds one complete level at a time, bounded by the tree's maximum width w.
def getLevel(self, root, target):
queue = collections.deque([root])
level = 1
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
if node.data == target:
return level
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
level += 1
return 0

Leaves at Same Level or Not​

Easy·

Check if all leaf nodes in a binary tree are at the same level. Return True if all leaves are at the same level, False otherwise.

3 Approachesclick to switch
FIG. LEAF AT SAME LEVEL● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • queue visits each of the tree's n nodes exactly once, level by level.
Space
O(w)
  • queue holds one complete level at a time, bounded by the tree's maximum width w.
def check(self, root):
queue = collections.deque([root])
first_leaf_level = None
level = 1
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
if not node.left and not node.right:
if not first_leaf_level:
first_leaf_level = level
elif first_leaf_level != level:
return False
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
level += 1
return True

Nodes at Odd Levels​

Easy·
FIG. NODES AT ODD LEVELS● INTERACTIVE
visualization loads as you reach it
Time
O(n + n log n)
  • The BFS visits every node once, O(n), collecting up to k odd-level values into results (worst case k = n).
  • sorted(results) then costs O(k log k), worst case O(n log n).
Space
O(sort + n)
  • queue holds one level at a time, bounded by the tree's width w <= n; results holds up to k <= n values.
  • Sorting algorithms are typically O(log n) space (in-place, recursion stack only), but Python's sorted() is Timsort, which allocates up to O(n) auxiliary space in the worst case - that's what sort stands for here.
def nodesAtOddLevels(self, root):
queue = collections.deque([root])
results = []
level = 1
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
if level % 2 == 1:
results.append(node.data)
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
level += 1
return sorted(results)

Next Right Node​

Easy·

Find the next right node of a given key in a binary tree. The next right node is the node that appears immediately to the right of the given key at the same level. If there's no such node, return a node with value -1.

3 Approachesclick to switch
FIG. NEXT RIGHT NODE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Each node is enqueued and dequeued exactly once level by level.
Space
O(w)
  • queue holds one complete level at a time, so it grows with the tree's max width w.
def nextRight(self, root, key):
queue = collections.deque([root])
while queue:
length = len(queue)
for i in range(length):
node = queue.popleft()
if node:
if node.data == key:
return queue[0] if queue and (i != length - 1) else Node(-1)
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
return Node(-1)

1609. Even Odd Tree​

Medium·

A binary tree is named Even-Odd if it meets the following conditions:

  • The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
  • For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
  • For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

3 Approachesclick to switch
FIG. EVEN ODD TREE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • Every node is popped from queue and checked exactly once across all n nodes.
Space
O(w)
  • queue holds one full level at a time, so it grows to w, the tree's maximum width.
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
queue = collections.deque([root])
level = 0
 
isEven = lambda i: i % 2 == 0
notLastNode = lambda i: queue and i != length - 1
 
while queue:
length = len(queue)
for i in range(length):
node = queue.popleft()
if node:
if isEven(level):
if isEven(node.val) or (
notLastNode(i) and node.val >= queue[0].val
):
return False
else:
if not isEven(node.val) or (
notLastNode(i) and node.val <= queue[0].val
):
return False
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
level += 1
return True

513. Find Bottom Left Tree Value​

Medium·

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

3 Approachesclick to switch
FIG. FIND BOTTOM LEFT TREE VALUE● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • The while queue loop dequeues every node exactly once via queue.popleft(), so total work across all levels is O(n), where n is the number of nodes.
Space
O(w)
  • queue holds at most one full level's worth of nodes - up to w nodes, where w is the tree's max width.
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
queue = collections.deque([root])
leftmost = None
while queue:
for i in range(len(queue)):
node = queue.popleft()
if node:
if i == 0:
leftmost = node.val if node else None
queue.append(node.left) if node.left else None
queue.append(node.right) if node.right else None
return leftmost