Part2

Level order Traversal

Example:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

🧠:
BFS

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root:
            return res

        queue = [root]
        while queue:
            curr = []
            for _ in range(len(queue)):
                node = queue.pop(0)
                curr.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            res.append(curr)
        return res

📘 💻

---

Height of Binary Tree

Example:

Input: root = [3,9,20,null,null,15,7]
Output: 3

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

📘 💻

---

Diamter of Binary Tree

Example:

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].

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.res = 0
        self.helper(root)
        return self.res

    def helper(self, node):
        if not node:
            return 0

        lh = self.helper(node.left)
        rh = self.helper(node.right)

        self.res = max(self.res, lh + rh)

        return 1 + max(lh, rh)

📘 💻

---

Balanced Binary Tree

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        self.res = True
        self.helper(root)
        return self.res

    def helper(self, node):
        if not node:
            return 0

        lh = self.helper(node.left)
        rh = self.helper(node.right)

        if abs(lh - rh) > 1:
            self.res = False

        return 1 + max(lh, rh)

📘 💻

---

LCA

Example:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

🧠:
1. Return None or Node in every recusive call for both left and right childs.
2. If both left and right recursive calls is not None, then current node is your answer.

class Solution:
    def lowestCommonAncestor(
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
    ) -> "TreeNode":
        if not root or p is root or q is root:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if None in (left, right):
            return left or right

        return root

📘 💻

---

Check if two trees are identical or not

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None:
            return q is None

        if q is None:
            return p is None

        return (
            p.val == q.val
            and self.isSameTree(p.left, q.left)
            and self.isSameTree(p.right, q.right)
        )

📘 💻

---

Zigzag Level Order Traversal

Example:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

🧠:
1. Use BFS
2. Use zig_zag flag at every level to zig zag the iteration.

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        if not root:
            return res

        queue = [root]
        zig_zag = 1

        while queue:
            curr_level = []

            for _ in range(len(queue)):
                curr_node = queue.pop(0)

                curr_level.append(curr_node.val)

                if curr_node.left:
                    queue.append(curr_node.left)
                if curr_node.right:
                    queue.append(curr_node.right)

            res.append(curr_level[::zig_zag])
            zig_zag *= -1

        return res

📘 💻

---

Boundary Traversal

❓: Given a Binary Tree, perform the boundary traversal of the tree. The boundary traversal is the process of visiting the boundary nodes of the binary tree in the anticlockwise direction, starting from the root.

Example:

Input:Binary Tree: 1 2 7 3 -1 -1 8 -1 4 9 -1 5 6 10 11
Output: Boundary Traversal: [1, 2, 3, 4, 5, 6, 10, 11, 9, 8, 7]

🧠:
1. Result is - root + left boundary excluding leaves + leaf nodes + reversed right boundary excluding leaves
2. Edge case - If root is leave node, return [root value]

class Solution:
    def traverseBoundary(self, root):
        # edge case: if root is leaf node
        if root.left is None and root.right is None:
            return [root.data]

        return (
            [root.data]
            + self.get_left_boundary(root.left)
            + self.get_leaves(root)
            + self.get_right_boundary(root.right)[::-1]
        )

    def get_left_boundary(self, node):
        res = []

        while node:
            if not (node.left is None and node.right is None):
                res.append(node.data)

            if node.left:
                node = node.left
            else:
                node = node.right

        return res

    def get_right_boundary(self, node):
        res = []

        while node:
            if not (node.left is None and node.right is None):
                res.append(node.data)

            if node.right:
                node = node.right
            else:
                node = node.left

        return res

    def get_leaves(self, node, leaves=[]):
        if node.left is None and node.right is None:
            leaves.append(node.data)

        if node.left:
            self.get_leaves(node.left)

        if node.right:
            self.get_leaves(node.right)

        return leaves

📘 💻

---