Part1

Populate Next Right pointers of Tree

❓: You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node { int val; Node *left; Node *right; Node *next; }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

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

🧠:
At each level, for every node, perform 2 steps a. make left next to right b. If node has any next, make right next as next left

class Solution:
    def connect(self, root: "Optional[Node]") -> "Optional[Node]":
        curr_level_head = root

        while curr_level_head and curr_level_head.left:
            temp = curr_level_head

            while temp:
                temp.left.next = temp.right
                if temp.next:
                    temp.right.next = temp.next.left
                temp = temp.next

            curr_level_head = curr_level_head.left

        return root

💻

---

Construct BST from given keys

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        n = len(nums)

        if n == 0:
            return
        if n == 1:
            return TreeNode(nums[0])

        mid = n // 2

        node = TreeNode(nums[mid])
        node.left = self.sortedArrayToBST(nums[:mid])
        node.right = self.sortedArrayToBST(nums[mid + 1 :])
        return node

💻

---

Construct a BST from a preorder traversal

🧠:
1. For BST, inorder will be sorted.
2. Find inorder by sorting preorder and construct BT.

class Solution:
    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
        return self.buildTree(preorder, sorted(preorder))

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return

        root_val = preorder.pop(0)
        node = TreeNode(root_val)

        root_inorder_ind = inorder.index(root_val)

        node.left = self.buildTree(
            preorder[:root_inorder_ind], inorder[:root_inorder_ind]
        )
        node.right = self.buildTree(
            preorder[root_inorder_ind:], inorder[root_inorder_ind + 1 :]
        )

        return node

💻

---

Check is a BT is BST or not

class Solution:
    def isValidBST(
        self, root: Optional[TreeNode], mini=float("-inf"), maxi=float("inf")
    ) -> bool:
        if not root:
            return True

        if not (mini < root.val < maxi):
            return False

        return self.isValidBST(root.left, mini, root.val) and self.isValidBST(
            root.right, root.val, maxi
        )

💻

---

Find LCA of two nodes in BST

class Solution:
    def lowestCommonAncestor(
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
    ) -> "TreeNode":
        curr = root

        while curr:
            if curr.val < p.val and curr.val < q.val:
                curr = curr.right

            elif curr.val > p.val and curr.val > q.val:
                curr = curr.left

            else:
                return curr

💻

---

Find the inorder predecessor/successor of a given Key in BST

❓: You are given root node of the BST and the key node of the tree. You need to find the in-order successor and predecessor of a given key. If either predecessor or successor is not found, then set it to NULL.

Note:- In an inorder traversal the number just smaller than the target is the predecessor and the number just greater than the target is the successor.

Example:

      8
    /   \
   1     9
   \      \
    4      10
   /
  3

key = 8
Output: 4 9

class Solution:
    def succPredBST(self, root, key):
        pred = succ = -1

        self.key = key

        curr = root

        while curr:
            if curr.data < key:
                pred = curr.data
                curr = curr.right
            else:
                curr = curr.left

        curr = root
        while curr:
            if curr.data > key:
                succ = curr.data
                curr = curr.left
            else:
                curr = curr.right

        return pred, succ

💻

---