Binary Tree¶
Table of Contents¶
- 104. Maximum Depth of Binary Tree (Easy)
- 100. Same Tree (Easy)
- 226. Invert Binary Tree (Easy)
- 101. Symmetric Tree (Easy)
- 105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)
- 106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)
- 117. Populating Next Right Pointers in Each Node II (Medium)
- 114. Flatten Binary Tree to Linked List (Medium)
- 112. Path Sum (Easy)
- 129. Sum Root to Leaf Numbers (Medium)
- 124. Binary Tree Maximum Path Sum (Hard)
- 173. Binary Search Tree Iterator (Medium)
- 222. Count Complete Tree Nodes (Easy)
- 236. Lowest Common Ancestor of a Binary Tree (Medium)
104. Maximum Depth of Binary Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def maxDepthRecursive(root: Optional[TreeNode]) -> int:
if not root:
return 0
left = maxDepthRecursive(root.left)
right = maxDepthRecursive(root.right)
return 1 + max(left, right)
# DFS
def maxDepthDFS(root: Optional[TreeNode]) -> int:
res = 0
def dfs(node, cnt):
if node is None:
return
cnt += 1
nonlocal res
res = max(res, cnt)
dfs(node.left, cnt)
dfs(node.right, cnt)
dfs(root, 0)
return res
# Iterative
def maxDepthIterative(root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
res = 0
while q:
res += 1
n = len(q)
for _ in range(n):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
if __name__ == "__main__":
root = [1, 2, 2, 3, 4, None, None, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \
# 3 4
# /
# 5
assert maxDepthRecursive(root) == 4
assert maxDepthDFS(root) == 4
assert maxDepthIterative(root) == 4
100. Same Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# 1. Recursive
def isSameTreeRecursive(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
elif not p or not q:
return False
elif p.val != q.val:
return False
return isSameTreeRecursive(p.left, q.left) and isSameTreeRecursive(p.right, q.right)
# 2. Iterative with queue
def isSameTreeIterativeQueue(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
queue = deque([(p, q)])
while queue:
p, q = queue.popleft()
if not p and not q:
continue
if not p or not q:
return False
if p.val != q.val:
return False
queue.append((p.left, q.left))
queue.append((p.right, q.right))
return True
# 3. Iterative with stack
def isSameTreeIterativeStack(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
stack = [(p, q)]
while stack:
n1, n2 = stack.pop()
if not n1 and not n2:
continue
if not n1 or not n2:
return False
if n1.val != n2.val:
return False
stack.append((n1.left, n2.left))
stack.append((n1.right, n2.right))
return True
if __name__ == "__main__":
p1 = build([1, 2, 3])
q1 = build([1, 2, 3])
p2 = build([1, 2])
q2 = build([1, None, 2])
assert isSameTreeRecursive(p1, q1) is True
assert isSameTreeRecursive(p2, q2) is False
assert isSameTreeIterativeQueue(p1, q1) is True
assert isSameTreeIterativeQueue(p2, q2) is False
assert isSameTreeIterativeStack(p1, q1) is True
assert isSameTreeIterativeStack(p2, q2) is False
226. Invert Binary Tree¶
from typing import Optional
from binarytree import build
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Recursive
def invertTreeRecursive(root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return root
root.left, root.right = root.right, root.left
invertTreeRecursive(root.left)
invertTreeRecursive(root.right)
return root
# Iterative
def invertTreeIterative(root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return root
stack = [root]
while stack:
node = stack.pop()
node.left, node.right = node.right, node.left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return root
root = build([4, 2, 7, 1, 3, 6, 9])
print(root)
# __4__
# / \
# 2 7
# / \ / \
# 1 3 6 9
invertedRecursive = invertTreeRecursive(root)
print(invertedRecursive)
# __4__
# / \
# 7 2
# / \ / \
# 9 6 3 1
root = build([4, 2, 7, 1, 3, 6, 9])
invertedIterative = invertTreeIterative(root)
print(invertedIterative)
# __4__
# / \
# 7 2
# / \ / \
# 9 6 3 1
101. Symmetric Tree¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def is_symmetric_recursive(root: Optional[TreeNode]) -> bool:
if not root:
return True
def check(left, right):
if left is right:
return True
if not left or not right or left.val != right.val:
return False
outside = check(left.left, right.right)
inside = check(left.right, right.left)
return outside and inside
return check(root.left, root.right)
# Iterative
def is_symmetric_iterative(root: Optional[TreeNode]) -> bool:
if not root:
return True
q = deque()
q.append(root.left)
q.append(root.right)
while q:
left = q.popleft()
right = q.popleft()
if not left and not right:
continue
if not left or not right or left.val != right.val:
return False
q.append(left.left)
q.append(right.right)
q.append(left.right)
q.append(right.left)
return True
if __name__ == "__main__":
root = [1, 2, 2, 3, 4, 4, 3]
root = build(root)
print(root)
# __1__
# / \
# 2 2
# / \ / \
# 3 4 4 3
assert is_symmetric_recursive(root) is True
assert is_symmetric_iterative(root) is True
#include <iostream>
#include "include/trees.hpp"
class Solution {
private:
bool dfs(TreeNode *Left, TreeNode *Right) {
if (Left == nullptr && Right == nullptr) return true;
if (Left == nullptr || Right == nullptr || Left->val != Right->val)
return false;
return dfs(Left->left, Right->right) && dfs(Left->right, Right->left);
}
public:
bool isSymmetric(TreeNode *root) {
return root == nullptr || dfs(root->left, root->right);
}
};
int main() {
Solution solution;
// Test with a symmetric tree
std::vector<int> values = {1, 2, 2, 3, 4, 4, 3};
TreeNode *root = TreeUtils::buildTree(values);
bool result = solution.isSymmetric(root);
std::cout << "Is symmetric: " << (result ? "true" : "false") << std::endl;
return 0;
}
105. Construct Binary Tree from Preorder and Inorder Traversal¶
from typing import List, Optional
from helper import TreeNode
def buildTree(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
"""
preorder root left right 1 2 3
inorder left root right 4 5 6
"""
if len(preorder) == 0:
return None
root_val = preorder[0] # 1
root = TreeNode(root_val)
separator_idx = inorder.index(root_val) # 5
left_inorder = inorder[:separator_idx] # 4
right_inorder = inorder[separator_idx + 1 :] # 6
left_preorder = preorder[1 : 1 + len(left_inorder)] # 2
right_preorder = preorder[1 + len(left_inorder) :] # 3
root.left = buildTree(left_preorder, left_inorder)
root.right = buildTree(right_preorder, right_inorder)
return root
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
root = buildTree(preorder, inorder)
print(root)
# 3
# / \
# 9 20
# / \
# 15 7
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right)
: val(x), left(left), right(right) {}
};
class Solution {
public:
vector<int> preorder;
unordered_map<int, int> inorderMap;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
for (size_t i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i;
}
return buildSubtree(0, 0, inorder.size() - 1);
}
private:
TreeNode* buildSubtree(int rootIndex, int left, int right) {
if (left > right) return nullptr;
TreeNode* root = new TreeNode(preorder[rootIndex]);
int inorderIndex = inorderMap[preorder[rootIndex]];
root->left = buildSubtree(rootIndex + 1, left, inorderIndex - 1);
root->right = buildSubtree(rootIndex + (inorderIndex - left + 1),
inorderIndex + 1, right);
return root;
}
};
int main() {
vector<int> preorder = {3, 9, 20, 15, 7};
vector<int> inorder = {9, 3, 15, 20, 7};
Solution solution;
TreeNode* root = solution.buildTree(preorder, inorder);
cout << root->val << endl; // 3
cout << root->left->val << endl; // 9
cout << root->right->val << endl; // 20
cout << root->right->left->val << endl; // 15
cout << root->right->right->val << endl; // 7
return 0;
}
106. Construct Binary Tree from Inorder and Postorder Traversal¶
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
"""
inorder: left root right 1 2 3
postorder: left right root 4 5 6
"""
if not postorder:
return None
root_val = postorder[-1] # 6
root = TreeNode(root_val)
separator_idx = inorder.index(root_val) # 2
left_inorder = inorder[:separator_idx] # 1
right_inorder = inorder[separator_idx + 1 :] # 3
left_postorder = postorder[: len(left_inorder)] # 4
right_postorder = postorder[len(left_inorder) : -1] # 5
root.left = buildTree(left_inorder, left_postorder)
root.right = buildTree(right_inorder, right_postorder)
return root
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
root = buildTree(inorder, postorder)
print(root)
# 3
# / \
# 9 20
# / \
# 15 7
117. Populating Next Right Pointers in Each Node II¶
from collections import deque
from typing import Optional
class Node:
def __init__(
self,
val: int = 0,
left: Optional["Node"] = None,
right: Optional["Node"] = None,
next: Optional["Node"] = None,
):
self.val = val
self.left = left
self.right = right
self.next = next
class connect:
def level_order(self, root: "Node") -> "Node":
if not root:
return None
q = deque([root])
while q:
size = len(q)
prev = None
for _ in range(size):
node = q.popleft()
if prev:
prev.next = node
prev = node
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
if __name__ == "__main__":
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(7)
# 1
# / \
# 2 3
# / \ \
# 4 5 7
solution = connect()
root = solution.level_order(root)
assert root.next is None
assert root.left.next == root.right
assert root.right.next is None
assert root.left.left.next == root.left.right
assert root.left.right.next == root.right.right
assert root.right.right.next is None
# 1 -> None
# / \
# 2 -> 3 -> None
# / \ \
# 4 -> 5 -> 7 -> None
114. Flatten Binary Tree to Linked List¶
#include <cassert>
#include <vector>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right)
: val(x), left(left), right(right) {}
};
class Solution {
public:
void flatten(TreeNode* root) {
if (!root) return;
flatten(root->left);
flatten(root->right);
TreeNode* left = root->left;
TreeNode* right = root->right;
root->left = nullptr;
root->right = left;
TreeNode* curr = root;
while (curr->right) curr = curr->right;
curr->right = right;
}
};
int main() {
Solution sol;
TreeNode* root =
new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)),
new TreeNode(5, nullptr, new TreeNode(6)));
sol.flatten(root);
TreeNode* cur = root;
std::vector<int> expected = {1, 2, 3, 4, 5, 6};
for (int val : expected) {
assert(cur != nullptr && cur->val == val);
cur = cur->right;
}
assert(cur == nullptr); // End of list
return 0;
}
112. Path Sum¶
from typing import Optional
from binarytree import build
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Recursive
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
if not root.left and not root.right:
return root.val == targetSum
targetSum -= root.val
return hasPathSum(root.left, targetSum) or hasPathSum(root.right, targetSum)
root = build([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, None, None, 1])
print(root)
# 5___
# / \
# ___4 _8
# / / \
# 11 13 4
# / \ \
# 7 2 1
print(hasPathSum(root, 22)) # True
129. Sum Root to Leaf Numbers¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
class sumNumbers:
def dfs(self, root: Optional[TreeNode]) -> int:
self.res = 0
def dfs(node, cur):
if not node:
return
cur = cur * 10 + node.val
if not node.left and not node.right:
self.res += cur
return
dfs(node.left, cur)
dfs(node.right, cur)
dfs(root, 0)
return self.res
if __name__ == "__main__":
root = [1, 2, 3]
root = build(root)
print(root)
# 1
# / \
# 2 3
assert sumNumbers().dfs(root) == 25
124. Binary Tree Maximum Path Sum¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
def maxPathSum(root: Optional[TreeNode]) -> int:
res = float("-inf")
def dfs(node):
if not node:
return 0
leftMax = max(dfs(node.left), 0)
rightMax = max(dfs(node.right), 0)
cur = node.val + leftMax + rightMax
nonlocal res
res = max(res, cur)
return node.val + max(leftMax, rightMax)
dfs(root)
return res
root = build([-10, 9, 20, None, None, 15, 7])
print(root)
# -10___
# / \
# 9 _20
# / \
# 15 7
print(maxPathSum(root)) # 42
173. Binary Search Tree Iterator¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# BST
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
self._leftmost_inorder(root)
def _leftmost_inorder(self, root):
while root:
self.stack.append(root)
root = root.left
def next(self) -> int:
topmost_node = self.stack.pop()
if topmost_node.right:
self._leftmost_inorder(topmost_node.right)
return topmost_node.val
def hasNext(self) -> bool:
return len(self.stack) > 0
root = build([7, 3, 15, None, None, 9, 20])
print(root)
# 7__
# / \
# 3 15
# / \
# 9 20
obj = BSTIterator(root)
print(obj.next()) # 3
print(obj.next()) # 7
print(obj.hasNext()) # True
222. Count Complete Tree Nodes¶
from collections import deque
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def countNodesRecursive(root: Optional[TreeNode]) -> int:
if not root:
return 0
num = 1 + countNodesRecursive(root.left) + countNodesRecursive(root.right)
return num
# Iterative
def countNodesIterative(root: Optional[TreeNode]) -> int:
if not root:
return 0
q = deque([root])
count = 0
while q:
n = len(q)
for _ in range(n):
node = q.popleft()
count += 1
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return count
# |------------|------- |---------|
# | Approach | Time | Space |
# |------------|--------|---------|
# | Recursive | O(n) | O(n) |
# | Iterative | O(n) | O(n) |
# |------------|--------|---------|
root = [1, 2, 3, 4, 5, 6]
root = build(root)
print(root)
# __1__
# / \
# 2 3
# / \ /
# 4 5 6
print(countNodesRecursive(root)) # 6
print(countNodesIterative(root)) # 6
236. Lowest Common Ancestor of a Binary Tree¶
from typing import List, Optional
from binarytree import build
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class LowestCommonAncestor:
def lowestCommonAncestor(
self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
) -> "TreeNode":
if not root or q == root or p == root:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right
if __name__ == "__main__":
root = build([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
print(root)
# ______3__
# / \
# 5__ 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
p = root.left # 5
q = root.right # 1
sol = LowestCommonAncestor()
print(sol.lowestCommonAncestor(root, p, q))
# ______3__
# / \
# 5__ 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right)
: val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) {
return root;
}
return left ? left : right;
}
};
int main() { return 0; }