Trees Flashcards
- Invert Binary Tree
Given the root of a binary tree, invert the tree, and return its root.
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root == None:
return
temp = root.left
root.left = root.right
root.right = temp
self.invertTree(root.left)
self.invertTree(root.right)
return root
** when we call a function within class definition. We prefix it with self.
- Check if root is None. Return None
- Swap root.left and root.right
- Call the function for left and right separately
- return root
Maximum Depth of Binary Tree
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.
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root == None:
return 0
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height,right_height)+1
- Check if root == Nonem return 0 as we are adding
- Get the left and right height by calling teh function
- we return 1 + max(left_height , right_height)
Diameter of Binary Tree
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.
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.diameter = 0 ## need this varible to be outside dfs to keep track
def height(root):
if root == None:
return 0
left_height = height(root.left)
right_height = height(root.right)
self.diameter = max(self.diameter, left_height + right_height)
return max(left_height,right_height)+1
height(root)
return self.diameter
** Declare diameter outside the recursive function that gets height. And make self.diameter as it is a class object and we need to keep track of it at all times
1. The code same as finding maxDepth. We just add a extra line for tracking diameter
diameter = max(diameter, left_height + right_height)
Balanced Binary Tree
Given a binary tree, determine if it is
height-balanced
Tree is balanced when :
1. left and right sides are balanced
and
2. when difference between left and right tree is atmost 1
.
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def balance(root):
if root == None:
return [True, 0]
left = balance(root.left)
right = balance(root.right)
left_height = left[1]
right_height = right[1]
left_is_balance = left[0]
right_is_balance = right[0]
if ((left_is_balance and right_is_balance) and (abs(left_height - right_height)<=1)):
return [True, max(left_height,right_height)+1]
else:
return [False, max(left_height,right_height)+1]
is_balance , height = balance(root)
return is_balance
Same Tree
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.
Only if all above pass, check children
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p== None and q == None:
return True
elif p == None or q == None:
return False
elif p.val != q.val:
return False
return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
- Check if both are leaf nodes. True. They had identical path
- Check if only 1 of them is leaf node. False. They dont have same path
- if they both are not leaf node. Then we check if the values are DISSIMILAR. if so, Then False.
- AND operation of left and right of p & q
** We choose to use DISSIMLARITY because :
Current Logic:
if p == None and q == None:
# return True # Both reached leaves - path is identical
# elif p == None or q == None:
# return False # Different structures
# elif p.val != q.val:
# return False # Different values
# return dfs(p.left,q.left) and dfs(p.right,q.right)
Problem with adding elif p.val == q.val: return True:
1 1 # / / \ # 2 2 3
These trees have same value at root (1) and left child (2)
# But they’re not identical trees!
# Need to check ALL nodes, not just current node values
Subtree of Another Tree
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.
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if root == None:
return False
if self.sameTree(root, subRoot):
return True
return self.isSubtree(root.left,subRoot) or self.isSubtree(root.right,subRoot)
def sameTree(self,p,q):
if p == None and q == None:
return True
elif p == None or q == None:
return False
elif p.val != q.val:
return False
return self.sameTree(p.left,q.left) and self.sameTree(p.right,q.right)
- we can see that we are using of sameTree() logic to check if root and subRoot are same
- And we do OR on isSubTree() to check if root.left or root.right is similar to subRoot
Lowest Common Ancestor of a Binary
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).”
class Solution:
def lowestCommonAncestor(self, root: ‘TreeNode’, p: ‘TreeNode’, q: ‘TreeNode’) -> ‘TreeNode’:
curr = root
while curr:
if p.val > curr.val and q.val > curr.val:
curr = curr.right
elif p.val < curr.val and q.val < curr.val:
curr = curr.left
else:
return curr
- In BST.
middle
small large - Thus if both the given value is larger or smaller than root then go to right and left repsectively.
- if 1 is smaller and 1 is larger. then it means we are where we want to be
Binary Tree Level Order Traversal
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).
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if root == None:
return []
q = deque()
q.append(root)
op = []
while q:
level = []
for i in range(len(q)):
current = q.popleft()
level.append(current.val)
if current.left:
q.append(current.left)
if current.right:
q.append(current.right)
op.append(level)
return op
Count Good Nodes in Binary Tree
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.
class Solution:
def goodNodes(self, root: TreeNode) -> int:
def dfs(node,maxval):
if node == None:
return 0
goodnode = 1 if node.val >= maxval else 0
maxval = max(node.val,maxval)
goodnode+= dfs(node.left,maxval)
goodnode+= dfs(node.right,maxval)
return goodnode
return dfs(root,-float('inf'))
We send root and the minimumest value of -inifinity to the dfs
a node is good when node.val >= maxval
And maxval will be changed as an when a node with higher value is spotted
We continue the search in left and right tree and add it.
Return the goodnode
Validate Binary Search Tree
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.
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def dfs(node, minval, maxval):
if node == None:
return True
if not (node.val < maxval and node.val > minval):
return False ## any instance where this condition occurs , thats it...false
left_valid = dfs(node.left,minval, node.val) #for left, min stays same. Max becomes current node val
right_valid = dfs(node.right,node.val,maxval) #for right, max stays same, Min becomes current node val
return left_valid and right_valid
return dfs(root, -float('inf'), float('inf'))
- We send root, -infinity, infinity to dfs
- In dfs we check the following condition is NOT met : left < middle < right. Then we send False
- If it does. We check on the left sub tree. But max becomes the current node val. Because we need the node.left < node
Similarly we go towards right sub tree. And min is the currren node val. Because we need node.right > node
Construct Binary Tree from Preorder and Inorder Traversal
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]
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0]) #preorder = root,left,right. We are creating a node for root
mid = inorder.index(preorder[0]) # inorder = Left, root, right. We try to find the index where root is in inorder
# the mid index allows us to know all the nodes that come on the left and right
# within those sub trees of left and right we get the form root by preorder
root.left = self.buildTree(preorder[1:mid+1],inorder[:mid])
root.right = self.buildTree(preorder[mid+1:],inorder[mid+1:])
return root
A # B C # D E F G
Inorder = [D B E A F C G]
# preorder = [A B D E C F G]
Binary Tree Maximum Path Sum
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.
’’’
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.max_sum = -float(‘inf’)## what if the root is negative
def dfs(node):
if node == None:
return 0
left_sum = max(dfs(node.left),0) # we ignore it if path sum is negative
right_sum = max(dfs(node.right),0)
current_path_sum = node.val + left_sum + right_sum
self.max_sum = max(self.max_sum, current_path_sum)
return node.val + max(left_sum, right_sum)
_ = dfs(root)
return self.max_sum '''
We go through each root.
We check for left_sum and right_sum. We make sure that they arent negative.
We calculate the current path sum = node.val + left_sum +right_sum
** we return pathsum that is — node.val + max(left_sum,right_sum) to the node above
— Reason on why we do max(dfs(node.left),0) similary for right sum. Intention is to ignore any path with negative sum
Let’s see this with a tree:
5
/
-3
\
-2
When we process -3 node:
Its right child (-2) returns -2
We take max(-2, 0) = 0 because:
If we include -2, our path sum decreases
Better to not include it at all (take 0)
Think of it as “cutting off” the negative path
Without max(sum, 0):
pythonCopy# If we didn’t use max(sum, 0)
5 + (-3) + (-2) = 0 # Including negative path
With max(sum, 0)
5 + 0 = 5 # Ignoring negative path is better!
