Simply Traverse
Simply DFS
Sum of Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
def sumBT(self, root):
def dfs(node):
if not node:
return 0
return node.data + dfs(node.left) + dfs(node.right)
return dfs(root)
Analysis
- Python
def sumBT(self, root):
stack = [root]
total = 0
while stack:
node = stack.pop()
if node:
total += node.data
stack.append(node.right)
stack.append(node.left)
return total
Analysis
- Python
def sumBT(self, root):
queue = collections.deque([root])
total = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
total += node.data
queue.append(node.left)
queue.append(node.right)
return total
Size of Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
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)
Analysis
- Python
def getSize(self, root: Optional["Node"]) -> int:
stack = [root]
size = 0
while stack:
node = stack.pop()
if node:
size += 1
stack.append(node.right)
stack.append(node.left)
return size
Analysis
- Python
def getSize(self, root: Optional["Node"]) -> int:
queue = collections.deque([root])
size = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
size += 1
queue.append(node.left)
queue.append(node.right)
return size
Count Leaves in Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
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)
Analysis
- Python
def countLeaves(self, root):
stack = [root]
size = 0
while stack:
node = stack.pop()
if node:
size += not node.left and not node.right
stack.append(node.right)
stack.append(node.left)
return size
Analysis
- Python
def countLeaves(self, root):
queue = collections.deque([root])
size = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
size += not node.left and not node.right
queue.append(node.left)
queue.append(node.right)
return size
Count Non-Leaf Nodes in Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
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)
Analysis
- Python
def countNonLeafNodes(self, root):
stack = [root]
size = 0
while stack:
node = stack.pop()
if node:
if node.left or node.right:
size += 1
stack.append(node.right)
stack.append(node.left)
return size
Analysis
- Python
def countNonLeafNodes(self, root):
queue = collections.deque([root])
size = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
if node.left or node.right:
size += 1
queue.append(node.left)
queue.append(node.right)
return size
Sum of Leaf Nodes
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
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)
Analysis
- Python
def leafSum(self, root):
stack = [root]
total = 0
while stack:
node = stack.pop()
if node:
if not node.left and not node.right:
total += node.data
stack.append(node.right)
stack.append(node.left)
return total
Analysis
- Python
def leafSum(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)
queue.append(node.right)
return total
Max and min element in Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
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)
Analysis
- Python
def findMax(self, root):
stack = [root]
maxi = -float("inf")
while stack:
node = stack.pop()
if node:
maxi = max(maxi, node.data)
stack.append(node.right)
stack.append(node.left)
return maxi
def findMin(self, root):
stack = [root]
mini = float("inf")
while stack:
node = stack.pop()
if node:
mini = min(mini, node.data)
stack.append(node.right)
stack.append(node.left)
return mini
Analysis
- Python
def findMax(self, root):
queue = collections.deque([root])
maxi = -float("inf")
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
maxi = max(maxi, node.data)
queue.append(node.left)
queue.append(node.right)
return maxi
def findMin(self, root):
queue = collections.deque([root])
mini = float("inf")
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
mini = min(mini, node.data)
queue.append(node.left)
queue.append(node.right)
return mini
Vertical Width of a Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
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
Analysis
- Python
def verticalWidth(self, root):
stack = [(root, 0)]
mini, maxi = float("inf"), -float("inf")
while stack:
node, col = stack.pop()
if node:
mini, maxi = min(mini, col), max(maxi, col)
stack.append((node.right, col + 1))
stack.append((node.left, col - 1))
return maxi - mini + 1 if mini != float("inf") else 0
Analysis
- Python
def verticalWidth(self, root):
queue = collections.deque([(root, 0)])
mini, maxi = float("inf"), -float("inf")
while queue:
for _ in range(len(queue)):
node, col = queue.popleft()
if node:
mini, maxi = min(mini, col), max(maxi, col)
queue.append((node.left, col - 1))
queue.append((node.right, col + 1))
return maxi - mini + 1 if mini != float("inf") else 0
1469. Find All The Lonely Nodes
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
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
Analysis
- Python
def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:
stack = [root]
lonely = []
while stack:
node = stack.pop()
if node:
if not node.left and node.right:
lonely.append(node.right.val)
if node.left and not node.right:
lonely.append(node.left.val)
stack.append(node.right)
stack.append(node.left)
return lonely
Analysis
- Python
def getLonelyNodes(self, root: Optional[TreeNode]) -> List[int]:
queue = collections.deque([root])
lonely = []
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
if not node.left and node.right:
lonely.append(node.right.val)
if node.left and not node.right:
lonely.append(node.left.val)
queue.append(node.right)
queue.append(node.left)
return lonely
965. Univalued Binary Tree
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
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)
Analysis
- Python
def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
stack = [root]
while stack:
node = stack.pop()
if node:
if node.val != root.val:
return False
stack.append(node.right)
stack.append(node.left)
return True
Analysis
- Python
def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
queue = collections.deque([root])
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
if node.val != root.val:
return False
queue.append(node.left)
queue.append(node.right)
return True
404. Sum of Left Leaves
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS
Analysis
- Python
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)
Analysis
- Python
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
stack = [root]
total = 0
is_leaf = lambda node: node and not node.left and not node.right
while stack:
node = stack.pop()
if node:
total += node.left.val if is_leaf(node.left) else 0
stack.append(node.right)
stack.append(node.left)
return total
Analysis
- Python
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
queue = collections.deque([root])
total = 0
is_leaf = lambda node: node and not node.left and not node.right
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
total += node.left.val if is_leaf(node.left) else 0
queue.append(node.left)
queue.append(node.right)
return total
1315. Sum of Nodes with Even-Valued Grandparent
Explanation
- DFS (Recursive)
- DFS (Iterative)
- BFS with Direct Grandchildren Access
Analysis
- Python
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)
Analysis
- Python
def sumEvenGrandparent(self, root: Optional[TreeNode]) -> int:
stack = [(root, False, -1, -1)]
total = 0
while stack:
node, visited, parent, gparent = stack.pop()
if node:
if visited:
total += node.val if gparent % 2 == 0 else 0
else:
stack.append((node, True, parent, gparent))
stack.append((node.right, False, node.val, parent))
stack.append((node.left, False, node.val, parent))
return total
Analysis
- Python
def sumEvenGrandparent(self, root: Optional[TreeNode]) -> int:
queue = collections.deque([root])
total = 0
getVal = lambda node: node.val if node else 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node:
if node.val % 2 == 0:
if node.left:
total += getVal(node.left.left) + getVal(node.left.right)
if node.right:
total += getVal(node.right.left) + getVal(node.right.right)
queue.append(node.left)
queue.append(node.right)
return total
Simply BFS
637. Average of Levels in Binary Tree
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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)
queue.append(node.right)
if count:
levels.append(total / count)
return levels
Analysis
- Python
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
def dfs(node, level):
if not node:
return
levels[level][0] += 1
levels[level][1] += node.val
dfs(node.left, level + 1)
dfs(node.right, level + 1)
levels = collections.defaultdict(lambda: [0, 0])
dfs(root, 0)
return [total / count for count, total in levels.values()]
Analysis
- Python
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
stack = [(root, 0)]
levels = collections.defaultdict(lambda: [0, 0])
while stack:
node, level = stack.pop()
if node:
levels[level][0] += 1
levels[level][1] += node.val
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return [total / count for count, total in levels.values()]
1302. Deepest Leaves Sum
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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
Analysis
- Python
def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
def dfs(node, level):
nonlocal maxi
if not node:
return
maxi = max(maxi, level)
if not node.left and not node.right:
levels[level] += node.val
dfs(node.left, level + 1)
dfs(node.right, level + 1)
levels = collections.defaultdict(int)
maxi = 0
dfs(root, 0)
return levels.get(maxi, 0)
Analysis
- Python
def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
stack = [(root, 0)]
levels = collections.defaultdict(int)
maxi = 0
while stack:
node, level = stack.pop()
if node:
maxi = max(maxi, level)
if not node.left and not node.right:
levels[level] += node.val
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return levels.get(maxi, 0)
1161. Maximum Level Sum of a Binary Tree
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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
Analysis
- Python
def maxLevelSum(self, root: Optional[TreeNode]) -> int:
def dfs(node, level):
if not node:
return
levels[level] += node.val
dfs(node.left, level + 1)
dfs(node.right, level + 1)
levels = collections.defaultdict(int)
dfs(root, 1)
return max(levels.items(), key=lambda x: x[1])[0]
Analysis
- Python
def maxLevelSum(self, root: Optional[TreeNode]) -> int:
stack = [(root, 1)]
levels = collections.defaultdict(int)
while stack:
node, level = stack.pop()
if node:
levels[level] += node.val
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return max(levels.items(), key=lambda x: x[1])[0]
Max Level Sum in Binary Tree
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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)
queue.append(node.right)
if total:
maxi = max(maxi, total)
return maxi
Analysis
- Python
def maxLevelSum(self, root):
def dfs(node, level):
nonlocal maxi
if not node:
return
levels[level] += node.data
dfs(node.left, level + 1)
dfs(node.right, level + 1)
levels = collections.defaultdict(int)
dfs(root, 0)
maxi = -float("inf")
for level_total in levels.values():
maxi = max(maxi, level_total)
return maxi
Analysis
- Python
def maxLevelSum(self, root):
stack = [(root, 0)]
levels = collections.defaultdict(int)
while stack:
node, level = stack.pop()
if node:
levels[level] += node.data
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
maxi = -float("inf")
for level_total in levels.values():
maxi = max(maxi, level_total)
return maxi
Largest value in each level
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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)
queue.append(node.right)
if maxi != -float("inf"):
result.append(maxi)
return result
Analysis
- Python
def largestValues(self, root):
def dfs(node, level):
if not node:
return
if level not in levels:
levels[level] = -float("inf")
levels[level] = max(levels[level], node.data)
dfs(node.left, level + 1)
dfs(node.right, level + 1)
levels = {}
dfs(root, 0)
return list(levels.values())
Analysis
- Python
def largestValues(self, root):
stack = [(root, 1)]
levels = {}
while stack:
node, level = stack.pop()
if node:
if level not in levels:
levels[level] = -float("inf")
levels[level] = max(levels[level], node.data)
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return list(levels.values())
Sum of Leaf Nodes at Min Level
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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)
queue.append(node.right)
if total != 0:
return total
return 0
Analysis
- Python
def minLeafSum(self, root):
def dfs(node, level):
nonlocal min_level, total
if not node:
return
if not node.left and not node.right:
if min_level > level:
total = 0
min_level = level
if level == min_level:
total += node.data
dfs(node.left, level + 1)
dfs(node.right, level + 1)
total, min_level = 0, float("inf")
dfs(root, 0)
return total
Analysis
- Python
def minLeafSum(self, root):
stack = [(root, 0)]
total, min_level = 0, float("inf")
while stack:
node, level = stack.pop()
if node:
if not node.left and not node.right:
if min_level > level:
total = 0
min_level = level
if level == min_level:
total += node.data
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return total
Odd even level difference
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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)
queue.append(node.right)
is_odd = not is_odd
return odd - even
Analysis
- Python
def getLevelDiff(self, root):
def dfs(node, level):
if not node:
return 0, 0
left_odd, left_even = dfs(node.left, level + 1)
right_odd, right_even = dfs(node.right, level + 1)
if level % 2:
return (node.data + left_odd + right_odd), (left_even + right_even)
else:
return (left_odd + right_odd), (node.data + left_even + right_even)
odd, even = dfs(root, 1)
return odd - even
Analysis
- Python
def getLevelDiff(self, root):
stack = [(root, 1)]
odd = even = 0
while stack:
node, level = stack.pop()
if node:
if level % 2:
odd += node.data
else:
even += node.data
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return odd - even
Maximum Width of Tree
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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)
queue.append(node.right)
max_width = max(max_width, width)
return max_width
Analysis
- Python
def maxWidth(self, root):
def dfs(node, level):
nonlocal max_width
if not node:
return
levels[level] += 1
max_width = max(max_width, levels[level])
dfs(node.left, level + 1)
dfs(node.right, level + 1)
max_width = 0
levels = collections.defaultdict(int)
dfs(root, 0)
return max_width
Analysis
- Python
def maxWidth(self, root):
stack = [(root, 0)]
levels = collections.defaultdict(int)
max_width = 0
while stack:
node, level = stack.pop()
if node:
levels[level] += 1
max_width = max(max_width, levels[level])
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return max_width
Maximum Node Level
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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)
queue.append(node.right)
if max_level_length < length:
max_level_length = length
max_level = level
level += 1
return max_level
Analysis
- Python
def maxNodeLevel(self, root):
def dfs(node, level):
nonlocal max_level, max_level_length
if not node:
return
levels[level] += 1
dfs(node.left, level + 1)
dfs(node.right, level + 1)
levels = collections.defaultdict(int)
dfs(root, 0)
max_level = max_level_length = 0
for level in levels:
if max_level_length < levels[level]:
max_level_length = levels[level]
max_level = level
return max_level
Analysis
- Python
def maxNodeLevel(self, root):
stack = [(root, 0)]
levels = collections.defaultdict(int)
while stack:
node, level = stack.pop()
if node:
levels[level] += 1
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
max_level = max_level_length = 0
for level in levels:
if max_level_length < levels[level]:
max_level_length = levels[level]
max_level = level
return max_level
Level of a Node in Binary Tree
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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)
queue.append(node.right)
level += 1
return 0
Analysis
- Python
def getLevel(self, root, target):
def dfs(node, level):
nonlocal result
if not node:
return
if node.data == target:
result = level
dfs(node.left, level + 1)
dfs(node.right, level + 1)
result = 0
dfs(root, 1)
return result
Analysis
- Python
def getLevel(self, root, target):
stack = [(root, 1)]
level = 1
while stack:
node, level = stack.pop()
if node:
if node.data == target:
return level
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return 0
Leaves at Same Level or Not
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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)
queue.append(node.right)
level += 1
return True
Analysis
- Python
def check(self, root):
def dfs(node, level):
nonlocal first_leaf_level
if not node:
return True
if not node.left and not node.right:
if not first_leaf_level:
first_leaf_level = level
elif first_leaf_level != level:
return False
left = dfs(node.left, level + 1)
right = dfs(node.right, level + 1)
return left and right
first_leaf_level = None
return dfs(root, 1)
Analysis
- Python
def check(self, root):
stack = [(root, 1)]
first_leaf_level = None
while stack:
node, level = stack.pop()
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
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return True
Nodes at Odd Levels
TODO: Geeks for Geeks platform is faulty for this problem, raised concern with the support team!
Next Right Node
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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)
Analysis
- Python
def nextRight(self, root, key):
def dfs(node, level):
nonlocal right_node, required_level
if not node:
return
if required_level == level:
right_node = node
required_level = None
if node.data == key:
required_level = level
dfs(node.left, level + 1)
dfs(node.right, level + 1)
required_level = None
right_node = Node(-1)
dfs(root, 0)
return right_node
Analysis
- Python
def nextRight(self, root, key):
stack = [(root, 0)]
required_level = None
while stack:
node, level = stack.pop()
if node:
if required_level == level:
return node
if node.data == key:
required_level = level
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return Node(-1)
1609. Even Odd Tree
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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
Analysis
- Python
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
def dfs(node, level):
if not node:
return True
if isEven(level):
if isEven(node.val) or (
notFirstNode(level) and node.val <= last_node[level]
):
return False
else:
if not isEven(node.val) or (
notFirstNode(level) and node.val >= last_node[level]
):
return False
last_node[level] = node.val
left_result = dfs(node.left, level + 1)
right_result = dfs(node.right, level + 1)
return left_result and right_result
last_node = {}
isEven = lambda i: i % 2 == 0
notFirstNode = lambda level: level in last_node
return dfs(root, 0)
Analysis
- Python
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
stack = [(root, 0)]
last_node = {}
isEven = lambda i: i % 2 == 0
notFirstNode = lambda level: level in last_node
while stack:
node, level = stack.pop()
if node:
if isEven(level):
if isEven(node.val) or (
notFirstNode(level) and node.val <= last_node[level]
):
return False
else:
if not isEven(node.val) or (
notFirstNode(level) and node.val >= last_node[level]
):
return False
last_node[level] = node.val
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return True
513. Find Bottom Left Tree Value
Explanation
- BFS
- DFS (Recursive)
- DFS (Iterative)
Analysis
- Python
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
Analysis
- Python
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
def dfs(node, level):
nonlocal max_level
if not node:
return
max_level = max(max_level, level)
if level not in levels:
levels[level] = node.val
dfs(node.left, level + 1)
dfs(node.right, level + 1)
levels = {}
max_level = 0
dfs(root, 0)
return levels[max_level]
Analysis
- Python
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
stack = [(root, 0)]
levels = {}
max_level = 0
while stack:
node, level = stack.pop()
if node:
max_level = max(max_level, level)
if level not in levels:
levels[level] = node.val
stack.append((node.right, level + 1))
stack.append((node.left, level + 1))
return levels[max_level]