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
