Easy Tree Questions

Tree

Tree is a collection of nodes connected by directed (or undirected) edges. A tree is a nonlinear data structure, compared to arrays, linked lists, stacks, and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.

 class TreeNode:
     def __init__(self, val=0, left=None, right=None):
         self.val = val
         self.left = left
         self.right = right

Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root

Example

Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]

Input: root = [2,1,3] Output: [2,3,1]

Approach 1:

I will implement a recursive method that in order to flip the values within a binary tree.

Implementation:

# recursive
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return root
        right, left = self.invertTree(self.right), self.invertTree(self.left)
        root.left, root.right = right, left
        return root
        

Approach 2:

It is always a good practice trying to implement a recursive call with an iterative approach.

Deque	Stack	Queue
append()	—	—
appendleft()	append()	append()
popleft()	—	pop()
pop()	pop()	—

In doing so, I will use the collections.deque object, which has these useful functions:

• append(x): add x to the right side of the deque
• appendleft(x): add x to the left side of the deque
• clear(): remove all elemenets from the deque leaving it with length 0
• count(x): count the number of deque elements equal to x
• extend(iterable): extend the right side of the deque by appending elements from the iterable argument –> also has extendleft(iterable)
• index(x): return the position of the x –> raises ValueError if not found
• insert(i,x): insert x into the deque at position i
• pop(): remove and return an element from the right side of the deque –> popleft()
• remove(value): remove the first occurrence of value –> raises ValueError if not found
• reverse(): reverse the elements of the deque in-place

Implementation:

# iterative
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        queue = collections.deque([root])
        while queue:
            current = queue.popleft()
            current.left, current.right = current.right, current.left
            if current.left:
                queue.append(current.left):
            if current.right:
                queue.append(current.right):
        
        return root
        

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.

Approach 1:

I had to come up with the base case where p and q are both None. Then, I will implement isSameTree that recursively checks if the values of the nodes for two trees are same.

Implementation:

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True:
        if p and q and p.val == q.val:
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right, q.right)
        else:
            return False
        

Approach 2:

It is always a good practice trying to implement a recursive call with an iterative DFS approach.

Implementation:

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        stack = [[p,q]]
        while stack:
            p,q = stack.pop()
            if not p and not q:
                continue
            elif p and q and p.val == q.val:
                stack.append([p.left, q.left])
                stack.append([p.right,q.right])
            else:
                return False
        return True

Maximum Depth of Binary Tree

Given the roots 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.

Approach 1:

Recursive DFS

Implementation:

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            if not root: return 0
            left, right = dfs(root.left), dfs(root.right)
            return max(left,right) + 1
        return dfs(root)

Approach 2:

Iterative DFS

Implementation:

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        stack, depth = [], 0
        stack.append((1,root))
        while stack != []:
            temp, root = stack.pop()
            if root is not None:
                depth = max(temp, depth)
                stack.append((temp+1, root.left))
                stack.append(temp+1, root.right))
        
        return depth
            

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.

Approach 1:

With DFS, find the maximum depth for each side recursively and update the height accordingly.

Implementation:

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        
        def dfs(root):
            if not root:
                return 0
            left, right = dfs(root.left), dfs(root.right)
            self.ans = max(self.ans, left + right)
            return max(left,right) + 1
        
        dfs(root)
        return self.ans

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

Approach 1:

A height-balanced tree refers to a tree where the difference of depth of left subtree and the right subtree is always less than or equal to 1.

Implementation:

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(root):
            if not root:
                return 0
            left, right = dfs(root.left), dfs(root.right)
            if  left == -1 or right == -1:
                return -1
            elif abs(left - right) > 1:
                return -1
            return max(left, right) +1
                
        return dfs(root) >= 0