Trees (binary/bst) Flashcards
- Invert Binary Tree
Solved
Easy
Topics
Companies
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3]
Output: [2,3,1]
Example 3:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
https://leetcode.com/problems/invert-binary-tree/description/
https://leetcode.com/problems/invert-binary-tree/description/
class TreeNode:
Definition for a binary tree node.
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root
- Maximum Depth of Binary Tree
Solved
Easy
Topics
Companies
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
Example 2:
Input: root = [1,null,2]
Output: 2
Constraints:
The number of nodes in the tree is in the range [0, 104].
-100 <= Node.val <= 100
https://leetcode.com/problems/maximum-depth-of-binary-tree/description/
class TreeNode:
Definition for a binary tree node.
~~~
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
~~~
- Diameter of Binary Tree
Solved
Easy
Topics
Companies Facebook
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100
https://leetcode.com/problems/diameter-of-binary-tree/description/
class TreeNode:
Definition for a binary tree node.
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def diameterRec(node):
if not node:
return 0,0
if not node.left and not node.right:
return 1,0
left_depth, ldiameter = diameterRec(node.left)
right_depth, rdiameter = diameterRec(node.right)
cur_diameter = left_depth + right_depth
maxDepth = max(left_depth, right_depth) + 1
maxDiameter = max(cur_diameter, ldiameter, rdiameter)
return maxDepth, maxDiameter
_, maxDiameter = diameterRec(root)
return maxDiameter
O(n), O(1) Space
- Balanced Binary Tree
Easy
Topics
Companies
Given a binary tree, determine if it is
height-balanced
.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3:
Input: root = []
Output: true
Constraints:
The number of nodes in the tree is in the range [0, 5000].
-104 <= Node.val <= 10
https://leetcode.com/problems/balanced-binary-tree/
class TreeNode:
Definition for a binary tree node.
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def recBalanced(node):
if not node:
return 0
leftdepth = recBalanced(node.left)
rightdepth = recBalanced(node.right)
if leftdepth < 0 or rightdepth < 0:
return -1
if abs(leftdepth - rightdepth) > 1:
return -1
else:
return max(leftdepth, rightdepth) + 1
return recBalanced(root) >= 0
- Same Tree
Solved
Easy
Topics
Companies
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
Constraints:
The number of nodes in both trees is in the range [0, 100].
-104 <= Node.val <= 104
https://leetcode.com/problems/same-tree/description/
https://leetcode.com/problems/same-tree/description/
class TreeNode:
Definition for a binary tree node.
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
curNode = True if (p and q and p.val == q.val) else False
if not curNode:
return False
return self.isSameTree(p.left, q.left) & self.isSameTree(p.right, q.right)
- Subtree of Another Tree
Solved
Easy
Topics
Companies
Hint
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.
Example 1:
Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Example 2:
Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Constraints:
The number of nodes in the root tree is in the range [1, 2000].
The number of nodes in the subRoot tree is in the range [1, 1000].
-104 <= root.val <= 104
-104 <= subRoot.val <= 104
https://leetcode.com/problems/subtree-of-another-tree/description/
https://leetcode.com/problems/subtree-of-another-tree/description/
class TreeNode:
Definition for a binary tree node.
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
curNode = True if (p and q and p.val == q.val) else False
if not curNode:
return False
return isSameTree(p.left, q.left) & isSameTree(p.right, q.right)
def subTree(root, subRoot):
if not root:
return False
curMatch = False
if root.val == subRoot.val:
curMatch = isSameTree(root, subRoot)
return curMatch or subTree(root.left, subRoot) or subTree(root.right, subRoot)
return subTree(root, subRoot)
- Binary Tree Level Order Traversal
Solved
Medium
Topics
Companies
Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000
https://leetcode.com/problems/binary-tree-level-order-traversal/description/
https://leetcode.com/problems/binary-tree-level-order-traversal/description/
Definition for a binary tree node.
from collections import deque
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def levelOrder(self, root):
“””
:type root: TreeNode
:rtype: List[List[int]]
“””
q = deque()
if root:
q.append(root)
ret = []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ret.append(level)
return ret
- Lowest Common Ancestor of a Binary Search Tree
Solved
Medium
Topics
Companies
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [2,1], p = 2, q = 1
Output: 2
Constraints:
The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the BST.
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
class TreeNode:
Definition for a binary tree node.
~~~
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: ‘TreeNode’, p: ‘TreeNode’, q: ‘TreeNode’) -> ‘TreeNode’:
def lca(root, p, q):
if root.val > p.val and root.val > q.val:
return lca(root.left, p, q)
elif root.val < p.val and root.val < q.val:
return lca(root.right, p, q)
else:
return root
return lca(root, p, q)
~~~
Iterative
Definition for a binary tree node.
~~~
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
“””
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
“””
cur = root
while cur:
if cur.val < p.val and cur.val < q.val:
cur = cur.right
elif cur.val > p.val and cur.val > q.val:
cur = cur.left
else:
return cur
~~~
- Binary Tree Right Side View
Solved
Medium
Topics
Companies Facebook
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Example 2:
Input: root = [1,null,3]
Output: [1,3]
Example 3:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
https://leetcode.com/problems/binary-tree-right-side-view/description/
Definition for a binary tree node.
from collections import deque
# Definition for a binary tree node.
# class TreeNode(object):
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
q = deque()
ret = []
q.append(root)
while q:
ret.append(q[0].val)
for i in range(len(q)):
node = q.popleft()
if node.right:
q.append(node.right)
if node.left:
q.append(node.left)
return ret
O(n), O(n)
- Count Good Nodes in Binary Tree
Solved
Medium
Topics
Companies
Hint
Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.
Return the number of good nodes in the binary tree.
Example 1:
Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.
Example 2:
Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because “3” is higher than it.
Example 3:
Input: root = [1]
Output: 1
Explanation: Root is considered as good.
Constraints:
The number of nodes in the binary tree is in the range [1, 10^5].
Each node’s value is between [-10^4, 10^4].
https://leetcode.com/problems/count-good-nodes-in-binary-tree/description/
Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def goodNodes(self, root: TreeNode) -> int:
def recGoodNodes(node, maxSofar):
if not node:
return 0
count = 0
if node.val >= maxSofar:
count +=1
maxSofar = max(maxSofar, node.val)
return recGoodNodes(node.left, maxSofar) + recGoodNodes(node.right, maxSofar) + count
return recGoodNodes(root, float('-inf'))
- Validate Binary Search Tree
Solved
Medium
Topics
Companies Amazon
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left
subtree
of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node’s value is 5 but its right child’s value is 4.
Constraints:
The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1
https://leetcode.com/problems/validate-binary-search-tree/description/
class TreeNode:
Definition for a binary tree node.
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def recIsValid(node, minimum, maximum):
if not node:
return True
if node.val <= minimum or node.val >= maximum:
return False
return recIsValid(node.left, minimum, node.val) and recIsValid(node.right, node.val, maximum)
return recIsValid(root, float('-inf'), float('inf'))
- Kth Smallest Element in a BST
Solved
Medium
Topics
Companies
Hint
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
Example 1:
Input: root = [3,1,4,null,2], k = 1
Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Constraints:
The number of nodes in the tree is n.
1 <= k <= n <= 104
0 <= Node.val <= 104
Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?
stack = []
cur = root
n=0
while stack and cur:
while cur:
stack.append(cur)
cur = cur.left
node = stack.pop()
n = n+1
if n == k:
return node.val
cur = node.right
return None
- Construct Binary Tree from Preorder and Inorder Traversal
Solved
Medium
Topics
Companies
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Constraints:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder and inorder consist of unique values.
Each value of inorder also appears in preorder.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
class TreeNode(object):
Definition for a binary tree node.
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def buildTree(self, preorder, inorder):
“””
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
“””
if len(preorder) == 0:
return None
if len(preorder) == 1:
return TreeNode(preorder[0])
root = preorder[0]
inorderPosRoot = inorder.index(root)
rightInorder = inorder[inorderPosRoot+1:]
leftInorder = inorder[:inorderPosRoot]
leftPreorder = preorder[1:len(leftInorder)+1]
rightPreOrder = preorder[len(leftInorder)+1:]
return TreeNode(root, self.buildTree(leftPreorder, leftInorder), self.buildTree(rightPreOrder, rightInorder))
- Binary Tree Maximum Path Sum
Hard
Topics
Companies Facebook DoorDash, Amazon
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Example 1:
Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.
Constraints:
The number of nodes in the tree is in the range [1, 3 * 104].
-1000 <= Node.val <= 1000
https://leetcode.com/problems/binary-tree-maximum-path-sum/description/
see if root + left and right is bigger than max so far,
Find gain from left and gain from right,
# return either the left path or right path as we can’t choose both.
Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def maxPathSum(self, root):
“””
:type root: TreeNode
:rtype: int
“””
def recMaxSum(node):
if not node:
return 0, float('-inf')
if not node.left and not node.right:
return node.val, node.val
leftSumA, leftSumB = recMaxSum(node.left)
rightSumA, rightSumB = recMaxSum(node.right)
gainFromLeft = max(leftSumA, 0)
gainFromRight = max(rightSumA, 0)
withParent = gainFromLeft + gainFromRight + node.val
maxSoFar = max(leftSumB, rightSumB, withParent)
return max(node.val + gainFromLeft, node.val + gainFromRight), maxSoFar
return max(recMaxSum(root))
- Serialize and Deserialize Binary Tree
Hard
Topics
Companies
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Example 1:
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Example 2:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
class TreeNode(object):
from collections import deque
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
def ser(node, nodes):
if not node:
return nodes + "$,"
left = ser(node.left, nodes)
right = ser(node.right, nodes)
return str(node.val) + "," + left + right
v = ser(root, "")
return v
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
spl = data.split(",")
q = deque(spl)
def deser(nodes):
if nodes[0] == "$":
nodes.popleft()
return None, nodes
node = TreeNode(nodes.popleft())
left, nodes = deser(nodes)
right, nodes = deser(nodes)
node.left = left
node.right = right
return node, nodes
root, v = deser(q)
return root
- Lowest Common Ancestor of a Binary Tree
Solved
Medium
Topics
Companies: Facebook,
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
Constraints:
The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the tree.
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
class TreeNode(object):
Definition for a binary tree node.
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
def rec(root, p ,q):
if not root:
return None
if root == p or root == q:
return root
left = rec(root.left, p, q)
right = rec(root.right, p, q)
if left and right:
return root
return (left or right)
return rec(root, p ,q)
https://leetcode.com/problems/range-sum-query-mutable/description/
- Range Sum Query - Mutable
Solved
Medium
Topics
Companies
Given an integer array nums, handle multiple queries of the following types:
Update the value of an element in nums.
Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.
Implement the NumArray class:
NumArray(int[] nums) Initializes the object with the integer array nums.void update(int index, int val) Updates the value of nums[index] to be val.int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + … + nums[right]).
Example 1:
Input
[“NumArray”, “sumRange”, “update”, “sumRange”]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]
Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2); // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8
class SegmentTree:
def \_\_init\_\_(self, nums):
self.nums = nums
self.n = len(nums)
self.tree = [0] * (2*self.n)
def create(self):
for i in range(self.n, 2*(self.n)):
self.tree[i] = self.nums[i-self.n]
for i in range((self.n)-1, -1,-1):
self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
def update(self, index, val):
tree_idx = index + self.n
self.tree[tree_idx] = val
while tree_idx > 0:
left = right = tree_idx
if left % 2:
left = tree_idx - 1
else:
right = tree_idx + 1
self.tree[tree_idx//2] = self.tree[left] + self.tree[right]
tree_idx //= 2
def sumRange(self, lbound, rbound):
lidx = lbound + self.n
ridx = rbound + self.n
res = 0
while lidx <= ridx:
if lidx % 2 == 1:
res += self.tree[lidx]
lidx +=1
if ridx % 2 == 0:
res += self.tree[ridx]
ridx -= 1
lidx //= 2
ridx //= 2
return res
class NumArray:
def \_\_init\_\_(self, nums: List[int]):
self.st = SegmentTree(nums)
self.st.create()
def update(self, index: int, val: int) -> None:
return self.st.update(index, val)
def sumRange(self, left: int, right: int) -> int:
return self.st.sumRange(left, right)https://leetcode.com/problems/my-calendar-i/description/
- My Calendar I
Solved
Medium
Topics
Companies
Hint
You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.
A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).
The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.
Implement the MyCalendar class:
MyCalendar() Initializes the calendar object. boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.
Example 1:
Input
[“MyCalendar”, “book”, “book”, “book”]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]
Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.
Constraints:
0 <= start < end <= 109 At most 1000 calls will be made to book.
class TreeNode(object):
def \_\_init\_\_(self, v=None, left=None, right=None):
self.v = v
self.left = left
self.right = right
class MyCalendar(object):
def \_\_init\_\_(self):
self.tree = TreeNode()
def book(self, start, end):
node = self.tree()
while True:
if not node.left and not node.right:
node.left = TreeNode(start)
node.right = TreeNode(end)
return True
def _book(self, start, end, node):
"""
:type start: int
:type end: int
:rtype: bool
"""
node = self.
if not node.left and not node.right:
node.left = TreeNode(start)
node.right = TreeNode(end)
return True
if end <= node.left.v:
return self._book(start, end, node.left)
elif start >= node.right.v:
return self._book(start,end, node.right)
else:
return False
class TreeNode:
def \_\_init\_\_(self, start, end):
self.s = start
self.e = end
self.l = None
self.r = None
class MyCalendar:
def \_\_init\_\_(self):
self.calendar = None
def book(self, start: int, end: int) -> bool:
if not self.calendar:
self.calendar = TreeNode(start, end)
return True
return self.insert(self.calendar, start, end)
def insert(self, node, s, e):
if e <= node.s:
if not node.l:
node.l = TreeNode(s, e)
return True
else:
return self.insert(node.l, s, e)
elif s >= node.e:
if not node.r:
node.r = TreeNode(s, e)
return True
else:
return self.insert(node.r, s, e)
else:
return False
Can be used as binary tree with ranges (l and right as individual nodes)
- Binary Tree Vertical Order Traversal
Facebook 2024
Given the root of a binary tree, return the vertical order traversal of its nodes’ values. (i.e., from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Example 2:
Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]
Example 3:
Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]
Constraints:
The number of nodes in the tree is in the range [0, 100]. -100 <= Node.val <= 100
https://leetcode.com/problems/binary-tree-vertical-order-traversal/
Definition for a binary tree node.
from collections import deque
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
store = [[] for _ in range(200)]
start = 99
start = 200
stop = -1
if not root:
return []
q = deque()
q.append((root, 99))
while q:
clen = len(q)
for _ in range(clen):
node, idx = q.popleft()
store[idx].append(node.val)
start = min(start, idx)
stop = max(stop, idx)
if node.left:
q.append((node.left, idx-1))
if node.right:
q.append((node.right, idx + 1))
return store[start:stop+1]
- Lowest Common Ancestor of a Binary Tree III
Solved
Medium
Topics
Companies
Hint
Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).
Each node will have a reference to its parent node. The definition for Node is below:
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}
According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1
Constraints:
The number of nodes in the tree is in the range [2, 105]. -109 <= Node.val <= 109 All Node.val are unique. p != q p and q exist in the tree.
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/description/
Space O(n) solution 1st pass 10 Mins
~~~
“””
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
“””
class Solution:
def lowestCommonAncestor(self, p: ‘Node’, q: ‘Node’) -> ‘Node’:
path_seen = set()
p_cur, q_cur = p,q
p_cur_pr, q_cur_pr = None, None
while p_cur or q_cur:
if p_cur == q_cur:
return p_cur
if p_cur and p_cur.val in path_seen:
return p_cur
if q_cur and q_cur.val in path_seen:
return q_cur
if p_cur:
path_seen.add(p_cur.val)
if q_cur:
path_seen.add(q_cur.val)
if p_cur:
p_cur_pr, p_cur = p_cur, p_cur.parent
if q_cur:
q_cur_pr, q_cur = q_cur, q_cur.parent ~~~
Better Solution O(1) extra Space:
Find the depth of both nodes, and make them reach equal depths. Then traverse up together. 2 passes effectively 1) to find the depths and 2nd to move them up.
"""
# Definition for a Node.
class Node:
def \_\_init\_\_(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution(object):
def lowestCommonAncestor(self, p, q):
"""
:type node: Node
:rtype: Node
"""
def depth(node):
depth = 0
while node:
depth += 1
node = node.parent
return depth
depth_p = depth(p)
depth_q = depth(q)
while depth_p > depth_q:
p = p.parent
depth_p -= 1
while depth_q > depth_p:
q = q.parent
depth_q -= 1
while p!=q:
p = p.parent
q = q.parent
return p
There is a clever solution to set p_pointer to q once it reaches the root node, and q_pointer to p once it reaches the root node.
Basically setting the higher placed node to the lower node once highest node reaches root.
Eventually they will meet because depth from p = a, and q = b
eg. if a is less, then by the time p_pointer reaches root, b will be b-a
once q_pointer reaches root and is set as p, p_pointer will be a depth away same as q_pointer now.
Thus now they will reach the same time up.
Would not recommend this solution for interview as it is not very intuitive and might show you have memorized the answers. But good to know since it might be useful in other problems.
class Solution:
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
a_node = p
b_node = q
while a_node != b_node:
if a_node.parent:
a_node = a_node.parent
else:
a_node = q
if b_node.parent:
b_node = b_node.parent
else:
b_node = p
return a_node
10 minutes
O(n) Space O(n) or O(1) depending what solution you use.
- Range Sum of BST
Easy
Companies: Facebook
Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].
Example 1:
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.
Example 2:
Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.
Constraints:
The number of nodes in the tree is in the range [1, 2 * 104]. 1 <= Node.val <= 105 1 <= low <= high <= 105 All Node.val are unique.
10 mins hard cap.
https://leetcode.com/problems/range-sum-of-bst/description/
Definition for a binary tree node.
# class TreeNode(object):
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def rangeSumBST(self, root, low, high):
"""
:type root: TreeNode
:type low: int
:type high: int
:rtype: int
"""
if not root:
return 0
if low <= root.val <= high:
return root.val + self.rangeSumBST(root.left, low, root.val) + self.rangeSumBST(root.right, root.val, high)
elif high < root.val:
return self.rangeSumBST(root.left, low, high)
elif low > root.val:
return self.rangeSumBST(root.right, low, high)
O(n), O(n) Space (call stack)
- Convert Binary Search Tree to Sorted Doubly Linked List
Medium
Companies: Facebook 2024
Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.
You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.
We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.
Example 1:
Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.
Example 2:
Input: root = [2,1,3]
Output: [1,2,3]
Constraints:
The number of nodes in the tree is in the range [0, 2000]. -1000 <= Node.val <= 1000 All the values of the tree are unique.
10 Minutes Optimal, 15 Minutes max alloted.
https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/description/
Definition for a Node.
"""
class Node:
def \_\_init\_\_(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
"""
class Solution(object):
def treeToDoublyList(self, root):
"""
:type root: Node
:rtype: Node
"""
def rec(node):
if not node:
return None, None
head, tail = node, node
if node.left:
left_head, left_tail = rec(node.left)
node.left = left_tail
left_tail.right = node
head = left_head
tail = node
if node.right:
right_head, right_tail = rec(node.right)
tail.right = right_head
right_head.left = tail
tail = right_tail
head.left = tail
tail.right = head
return head, tail
head, tail = rec(root)
return head
O(n), O(n)
- Sum Root to Leaf Numbers
Solved
Medium
Topics
Companies: Meta
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
Example 1:
Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Example 2:
Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
Constraints:
The number of nodes in the tree is in the range [1, 1000]. 0 <= Node.val <= 9 The depth of the tree will not exceed 10.
O(n), O(n)
https://leetcode.com/problems/sum-root-to-leaf-numbers/description/
Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
nums = []
def rec(num, node):
if not node:
return
num = (num * 10) + node.val
if not node.left and not node.right:
nums.append(num)
return
rec(num, node.left)
rec(num, node.right)
rec(0, root)
return sum(nums)
- Closest Binary Search Tree Value
Solved
Easy
Topics
Companies
Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest.
Example 1:
Input: root = [4,2,5,1,3], target = 3.714286
Output: 4
Example 2:
Input: root = [1], target = 4.428571
Output: 1
Constraints:
The number of nodes in the tree is in the range [1, 104].
0 <= Node.val <= 109
-109 <= target <= 109
https://leetcode.com/problems/closest-binary-search-tree-value/description/
2 Ways, recursive, O(Long(n)) time space, and Linear, same time but O(1) space.
# Definition for a binary tree node.
# class TreeNode(object):
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def closestValue(self, root, target):
"""
:type root: TreeNode
:type target: float
:rtype: int
"""
# This one line saves around 12 lines of code throughout the program. Credit: @stefanpochmann.
smallest_fn = lambda a, b: min(a, b, key=lambda x: (abs(target-x), x))
def rec(node, previous, target):
if not node:
return previous
smallest = smallest_fn(previous, node.val)
node = node.left if node.val > target else node.right
closest_sub = rec(node, smallest, target)
return smallest_fn(smallest, closest_sub)
return rec(root, root.val, target)
Iterative: OG: @stefanpochmann
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
smallest_fn = lambda a, b: min(a, b, key=lambda x: (abs(target-x), x))
smallest = root.val
while root:
smallest = smallest_fn(root.val, smallest)
root = root.left if root.val > target else root.right
return smallest
- Vertical Order Traversal of a Binary Tree
Solved
Hard
Topics
Companies
Given the root of a binary tree, calculate the vertical order traversal of the binary tree.
For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).
The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.
Return the vertical order traversal of the binary tree.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.
Example 2:
Input: root = [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
1 is at the top, so it comes first.
5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.
Example 3:
Input: root = [1,2,3,4,6,5,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.
Constraints:
The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 1000
Sort Order for column: Row, value
https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/description/
from collections import deque, defaultdict
from sortedcontainers import SortedList
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
q = deque()
q.append((root, 0))
row = 0
min_range = float('inf')
max_range = float('-inf')
storage = defaultdict(lambda: SortedList(key=lambda x: (row, x)))
while q:
qlen = len(q)
for _ in range(qlen):
node, col = q.popleft()
min_range = min(min_range, col)
max_range = max(max_range, col)
storage[col].add(node.val)
if node.left:
q.append((node.left, col-1))
if node.right:
q.append((node.right, col+1))
row += 1
output = []
for i in range(min_range, max_range+1):
output.append(storage[i])
return output- Closest Binary Search Tree Value II
Solved
Hard
Topics
Companies
Hint
Given the root of a binary search tree, a target value, and an integer k, return the k values in the BST that are closest to the target. You may return the answer in any order.
You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
Example 1:
Input: root = [4,2,5,1,3], target = 3.714286, k = 2
Output: [4,3]
Example 2:
Input: root = [1], target = 0.000000, k = 1
Output: [1]
Constraints:
The number of nodes in the tree is n.
1 <= k <= n <= 104.
0 <= Node.val <= 109
-109 <= target <= 109
Follow up: Assume that the BST is balanced. Could you solve it in less than O(n) runtime (where n = total nodes)?
https://leetcode.com/problems/closest-binary-search-tree-value-ii/
from collections import deque
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
vals = deque()
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
dist = abs(cur.val - target)
if len(vals) >= k and vals[0][0] > dist:
vals.popleft()
if len(vals) < k:
vals.append((dist, cur.val))
cur = cur.right
return [v[1] for v in vals]
O(n), O(n) <- stack space
- Find Leaves of Binary Tree
Medium
Given the root of a binary tree, collect a tree’s nodes as if you were doing this:
Collect all the leaf nodes.
Remove all the leaf nodes.
Repeat until the tree is empty.
Example 1:
Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.
Example 2:
Input: root = [1]
Output: [[1]]
Constraints:
The number of nodes in the tree is in the range [1, 100].
-100 <= Node.val <= 100
https://leetcode.com/problems/find-leaves-of-binary-tree/
from collections import defaultdict
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
leaf = defaultdict(list)
def rec(node):
nonlocal leaf
if not node:
return -1
val_l = rec(node.left)
val_r = rec(node.right)
valthis = max(val_l, val_r) + 1
leaf[valthis].append(node.val)
return valthis
rec(root)
return leaf.values()
O(n) time O(n) space
