[Python] template Tree questions in One Place for quick revision

1126

Creating a quick revision guide for Tree questions. There can be more optimized version of the solution available.

DFS Traversal:
Inorder: https://leetcode.com/problems/binary-tree-inorder-traversal/

#Recursive
def inorderTraversal(self, root):
    res = []
    self.helper(root, res)
    return res
    
def helper(self, root, res):
    if root:
        self.helper(root.left, res)
        res.append(root.val)
        self.helper(root.right, res)

#iterative
def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack,res = [],[]
        while stack or root:
            if root:
                stack.append(root)
                root = root.left
            else:
                node = stack.pop()
                res.append(node.val)
                root = node.right
        return res

preorder: https://leetcode.com/problems/binary-tree-preorder-traversal/

# recursive
def preorderTraversal(self, root):
    res = []
    self.dfs(root, res)
    return res
    
def dfs(self, root, res):
    if root:
        res.append(root.val)
        self.dfs(root.left, res)
        self.dfs(root.right, res)

#iterative
def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack,res = [],[]
        while stack or root:
            if root:
                stack.append(root)
                res.append(root.val)
                root = root.left
            else:
                node = stack.pop()
                root = node.right
        return res

postorder: https://leetcode.com/problems/binary-tree-postorder-traversal/

#recursive
def postorderTraversal(self, root):
    res = []
    self.dfs(root, res)
    return res
    
def dfs(self, root, res):
    if root:
        self.dfs(root.left, res)
        self.dfs(root.right, res)
		res.append(root.val)

#iterative
def postorderTraversal(self, root: TreeNode) -> List[int]:
        stack,res = [],[]
        while stack or root:
            if root:
                stack.append(root)
                res.append(root.val)
                root = root.right
            else:
                node = stack.pop()
                root = node.left
        return res[::-1]

BFS traversal:
Level order:

def level(root):
    queue = [root]
    levels = []
    while queue:
        ele = queue.pop(0)
        levels.append(ele.val)
        if ele.left:queue.append(ele.left)
        if ele.right:queue.append(ele.right)
    return levels

Level order travels: level by level
problem: https://leetcode.com/problems/binary-tree-level-order-traversal/

def level(root):
    queue = [root,None]
    levels = []
    currNode = []
    while queue:
        ele = queue.pop(0)
        if ele:
            currNode.append(ele.val)
            if ele.left:queue.append(ele.left)
            if ele.right:queue.append(ele.right)
        else:
            levels.append(currNode)
            if queue:
                queue.append(None)
                currNode = []    
    return levels

Zigzag traversal
problem: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

from collections import deque
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        queue = deque([(root,0)])
        levels,ans = [],[]
        while queue:
            x, level = queue.popleft()
            if x:
                if level == len(levels):
                    levels.append([])
                levels[level].append(x.val)
                queue.append((x.left,level+1))
                queue.append((x.right,level+1))
        for i in range(len(levels)):
            if i%2 == 0:
                ans.append(levels[i])
            else:
                ans.append(levels[i][::-1])
              
        return ans

Diffrent views of tree:
Left view:

#Recursive
def findBottomLeftValue(self, root: TreeNode) -> int:
        self.ans = []
        self.max_level = -1
        self.dfs(root, 0)
        return self.ans
    def dfs(self, root, depth):
        if not root:return
        if depth > self.max_level:
            self.max_level = depth
            self.ans.append(root.val)
        self.dfs(root.left, depth + 1)
        self.dfs(root.right, depth + 1)
		
#iterative
 def findBottomLeftValue(self, root: TreeNode) -> int:
        queue = deque([(root,0)])
        levels,ans = [],[]
        while queue:
            x,level = queue.popleft()
            if x:
                if level == len(levels):
                    levels.append([])
                levels[level].append(x.val)
                queue.append((x.left,level+1))
                queue.append((x.right,level+1))
        for level in levels:
            ans.append(level[0])
        return ans

Right view:
problem: https://leetcode.com/problems/binary-tree-right-side-view/

#recursive
def rightView(root,max1,level,res):
    if root == None:
        return
    if max1[0] < level:
        res.append(root.val)
        max1[0] = level   
    rightView(root.right,max1,level+1,res)
    rightView(root.left,max1,level+1,res)

#iterative
def rightSideView(self, root: TreeNode) -> List[int]:
        if root == None:
            return []
        queue = deque([(root,0)])
        levels,ans = [],[]
        while queue:
            x,level = queue.popleft()
            if x:
                if len(levels) == level:
                    levels.append([])
                levels[level].append(x.val)
                queue.append((x.left,level+1))
                queue.append((x.right,level+1))
        # print(levels)
        for i in levels:
            ans.append(i[-1])
        return res

Comments (0)