Skip to main content

Simply Traverse

Simply DFS​

Sum of Binary Tree​

Sum of Binary Tree

Basic3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Size of Binary Tree

Basic3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Count Leaves in Binary Tree

Basic3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Count Non-Leaf Nodes in Tree

Basic3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Sum of Leaf Nodes

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Max and min element in Binary Tree

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Vertical Width of a Binary Tree

Medium3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

1469. Find All The Lonely Nodes

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

965. Univalued Binary Tree

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

404. Sum of Left Leaves

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Medium3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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)

Simply BFS​

637. Average of Levels in Binary Tree​

637. Average of Levels in Binary Tree

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

1302. Deepest Leaves Sum

Medium3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Medium3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Max Level Sum in Binary Tree

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Largest value in each level

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Sum of Leaf Nodes at Min Level

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Odd even level difference

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Maximum Width of Tree

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Maximum Node Level

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Level of a Node in Binary Tree

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Leaves at Same Level or Not

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

Nodes at Odd Levels

Easy1 solutionanalysis1 playground
Solutions:

Analysis

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​

Next Right Node

Easy3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

1609. Even Odd Tree

Medium3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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​

513. Find Bottom Left Tree Value

Medium3 solutionsexplanationanalysis1 playground

Explanation

Solutions:

Analysis

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