Trees¶
Table of Contents¶
- 226. Invert Binary Tree (Easy)
- 104. Maximum Depth of Binary Tree (Easy)
- 100. Same Tree (Easy)
- 572. Subtree of Another Tree (Easy)
- 235. Lowest Common Ancestor of a Binary Search Tree (Medium)
- 102. Binary Tree Level Order Traversal (Medium)
- 98. Validate Binary Search Tree (Medium)
- 230. Kth Smallest Element in a BST (Medium)
- 105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)
- 124. Binary Tree Maximum Path Sum (Hard)
- 298. Binary Tree Longest Consecutive Sequence (Medium) 👑
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
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
572. Subtree of Another Tree¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# DFS - Tree
def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def isSameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
if not root:
return False
return (
isSameTree(root, subRoot)
or isSubtree(root.left, subRoot)
or isSubtree(root.right, subRoot)
)
# |------------|---------|----------|
# | Approach | Time | Space |
# |------------|---------|----------|
# | DFS | O(n * m)| O(n) |
# |------------|---------|----------|
root = build([3, 4, 5, 1, 2, None, None, None, None, 0])
subRoot = build([4, 1, 2])
print(root)
# ____3
# / \
# 4__ 5
# / \
# 1 2
# /
# 0
print(subRoot)
# 4
# / \
# 1 2
print(isSubtree(root, subRoot)) # False
235. Lowest Common Ancestor of a Binary Search Tree¶
from binarytree import build
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def lowestCommonAncestor(
root: "TreeNode", p: "TreeNode", q: "TreeNode"
) -> "TreeNode":
while root:
if root.val > p.val and root.val > q.val:
root = root.left
elif root.val < p.val and root.val < q.val:
root = root.right
else:
return root
root = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5]
root = build(root)
p = root.left
q = root.right
print(root)
# ______6__
# / \
# 2__ 8
# / \ / \
# 0 4 7 9
# / \
# 3 5
print(lowestCommonAncestor(root, p, q))
# ______6__
# / \
# 2__ 8
# / \ / \
# 0 4 7 9
# / \
# 3 5
102. Binary Tree Level Order Traversal¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
q = deque([root])
res = []
while q:
level = []
size = len(q)
for _ in range(size):
cur = q.popleft()
level.append(cur.val)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
res.append(level)
return res
tree = build([3, 9, 20, None, None, 15, 7])
print(tree)
# 3___
# / \
# 9 _20
# / \
# 15 7
print(levelOrder(tree)) # [[3], [9, 20], [15, 7]]
98. Validate Binary Search Tree¶
from itertools import pairwise
from math import inf
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
def isValidBST1(root: Optional[TreeNode]) -> bool:
inorder = [] # inorder traversal
def dfs(node):
if not node:
return None
dfs(node.left)
inorder.append(node.val)
dfs(node.right)
dfs(root)
for a, b in pairwise(inorder):
if a >= b:
return False
return True
def isValidBST2(root: Optional[TreeNode]) -> bool:
if not root:
return True
pre = -inf
def dfs(node):
if not node:
return True
if not dfs(node.left):
return False
nonlocal pre
if node.val <= pre:
return False
pre = node.val
return dfs(node.right)
return dfs(root)
if __name__ == "__main__":
root = [5, 1, 4, None, None, 3, 6]
root = build(root)
print(root)
# 5__
# / \
# 1 4
# / \
# 3 6
assert not isValidBST1(root) # [1, 5, 3, 4, 6]
assert not isValidBST2(root) # [1, 5, 3, 4, 6]
#include <cassert>
#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 {
private:
vector<int> inorder;
bool check(vector<int> inorder) {
int n = inorder.size();
if (n <= 1) return true;
for (int i = 1; i < n; i++) {
if (inorder[i] <= inorder[i - 1]) return false;
}
return true;
}
public:
bool isValidBST(TreeNode *root) {
auto dfs = [&](auto &&self, TreeNode *node) -> void {
if (!node) return;
self(self, node->left);
inorder.push_back(node->val);
self(self, node->right);
};
dfs(dfs, root);
return check(inorder);
}
};
int main() {
Solution s;
TreeNode *root = new TreeNode(2);
root->left = new TreeNode(1);
root->right = new TreeNode(3);
assert(s.isValidBST(root) == true);
root = new TreeNode(5);
root->left = new TreeNode(1);
root->right = new TreeNode(4);
root->right->left = new TreeNode(3);
root->right->right = new TreeNode(6);
assert(s.isValidBST(root) == false);
root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(6);
root->right->left = new TreeNode(3);
root->right->right = new TreeNode(7);
assert(s.isValidBST(root) == false);
return 0;
}
230. Kth Smallest Element in a BST¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Recursive
def kthSmallestRecursive(root: Optional[TreeNode], k: int) -> int:
inorder = []
def dfs(node):
if not node:
return None
dfs(node.left)
inorder.append(node.val)
dfs(node.right)
dfs(root)
return inorder[k - 1]
# Iteratve
def kthSmallestIteratve(root: Optional[TreeNode], k: int) -> int:
stack = []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if not k:
return root.val
root = root.right
if __name__ == "__main__":
root = build([3, 1, 4, None, 2])
k = 1
assert kthSmallestRecursive(root, k) == 1
assert kthSmallestIteratve(root, k) == 1
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;
}
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
298. Binary Tree Longest Consecutive Sequence¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# Binary Tree
def longestConsecutive(root: Optional[TreeNode]) -> int:
res = 0
def dfs(node):
if not node:
return 0
left, right = dfs(node.left), dfs(node.right)
cur = 1
if node.left and node.left.val == (node.val + 1):
cur = max(cur, left + 1)
if node.right and node.right.val == (node.val + 1):
cur = max(cur, right + 1)
nonlocal res
res = max(res, cur)
return cur
dfs(root)
return res
if __name__ == "__main__":
root = build([1, 3, 2, 4, None, None, None, 5])
print(root)
# 1
# / \
# 3 2
# /
# 4
# /
# 5
print(longestConsecutive(root)) # 3