Author: devangini123

🌙 Array representation of Heap: We are using array’s to represent heap. We can also represent heap using pointers or references. MinHeap Representation Using Level Order traversal arr[0] = smallest_Element smallest_Element = O(1) Time Complexity heap[0] = O(1) Binary Tree representation using Array All the empty spaces are represented by ‘#’ MaxHeap Representation maxElement = heap[0] Have to find Children of ith node: Formula’s based on index 1 left = 2 * i right = 2 * i + 1 parent = ith Formula’s based on index 0 left = (2*i + 1) right = (2*i + 2) parent =…

🌙 Complete Binary Tree: A Complete Binary Tree is one in which, during level order traversal, there are no missing nodes. All levels are completely filled except possibly the last level, which is filled from left to right. Full Binary Tree: Every full binary tree is always a complete binary tree. At every level, all the nodes are present. You need to fill all the nodes at each level before moving to the next. The number of nodes at each level is2n n is the level number (starting from 0). Important Points to Remember: A complete binary tree is a…

Binary Search Tree: BST is a special type of Binary Tree with atmost 2 childern. For Every Node: All nodes of left subtree have smaller value. All node of right subtree have greater value. Important Point to Note: All the subtrees of a tree should be BST. A tree is a Binary Search Tree only if every node follows the BST rules. Valid BST Why it is called a Search Tree ? Search the value 75: Here, we are finding it in a very easy way — we don’t need to check unnecessary nodes. At every iteration, the search space…

Problem Statement: Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Examples: Example 1: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6. Example 2: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p =…

Problem Statement: Given the root of a binary search tree, and an integer k, return the th smallest value (1-indexed) of all the values of the nodes in the tree. Examples: Example 1: Input: root = [3,1,4,null,2], k = 1 Output: 1 Example 2: Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3 Example 3: Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 Output: [4,2,7,1,3,5] Constraints: The number of nodes in the tree is n. 1

Problem Statement: You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them. Examples: Example 1: Input: root = [4,2,7,1,3], val = 5 Output: [4,2,7,1,3,5] Explanation: Another accepted tree is: Example 2: Input: root = [40,20,60,10,30,50,70], val = 25 Output:…

Problem Statement: You are given the root of a binary search tree (BST) and an integer val. Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null. Examples: Example 1: Input: root = [4,2,7,1,3], val = 2 Output: [2,1,3] Example 2: Input: root = [4,2,7,1,3], val = 5 Output: [] Constraints: The number of nodes in the tree is in the range [1, 5000]. 1

Problem Statement: Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys strictly less than the node’s key. The right subtree of a node contains only nodes with keys strictly greater than the node’s key. Both the left and right subtrees must also be binary search trees. Examples: Example 1: Input: root = [2,1,3] Output: true Example 2: Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node’s value is 5 but its right child’s…

Problem Statement: A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node’s values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path. Examples: Example 1: Input: root = [1,2,3] Output: 6 Explanation: The optimal path is 2 -> 1 ->…

Problem Statement: 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. Examples: Example 1: Input: root = [1,2,3,4,5,6,7] Output: [1,#,2,3,#,4,5,6,7,#] Explanation: Given the above perfect binary tree (Figure A), your function should populate each next…