Leetcode: Trees

We are going to discuss several basic algorithms related to trees and some related to binary search trees.

As the structure of children is same as that of the root, problems can easily be broken down. We can recursively solve problems for all children of the root and then combine the results.

The time complexity of such algorithms will be height of tree multiplied by complexity of combining results.

Space complexity for recursions will be poor as with each recursive call we are creating a new set of all the variables used in our program. Since recursion will run on all the nodes the space complexity will be O(n)

Maximum Depth of Binary Tree | LeetCode OJ

1. Find the depth of the left child recursively
2. Find the depth of the right child recursively
3. Pick the maximum
4. Complexity if O(n) as program will run for all nodes

# 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 maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        height_left = self.maxDepth(root.left)
        height_right = self.maxDepth(root.right)
        return 1 + max(height_left, height_right) if root else 0

Invert Binary Tree | LeetCode OJ

In simple words we need to create a mirror copy of the tree, again an easy recursive solutions is

1. Invert the left subtree and make it right child
2. Invert the right subtree and make it left child
3. return the root

if root:
    root.left = self.invertTree(root.right)
    root.right = self.invertTree(root.left)
return root

Same Tree | LeetCode OJ

Checking if the given trees are same can be done by checking if roots and children are same

1. Check if the root values match
2. Recursively check if left subtree matches
3. Recursively check if right subtree matches

I have added a one liner solutions as well

def isSameTree(self, p, q):
    if p is None and q is None:
        return True
    if p is not None and q is not None:
        c1 = p.val == q.val
        c2 = self.isSameTree(p.left, q.left)
        c3 = self.isSameTree(p.right, q.right)
        return c1 and c2 and c3
    return False
def isSameTree(self, p, q):
    return p is None and q is None or 
p is not None and 
q is not None and 
(p.val == q.val) and 
(self.isSameTree(p.left, q.left) and 
self.isSameTree(p.right, q.right))