Author: devangini123

🌙 Deleting (Extracting) Elements from a Heap Min Heap: Extraction only happen from the top = heap[0]. Heapify down is the process of restoring the heap property after removing the root element (or moving an element downwards). MinHeap is formed. Practice: Solution: Min Heap is formed. Code class MinHeap { constructor() { this.heap = [5, 10, 20, 30]; } getLeftChildIndex(i) { return (2 * i) + 1; } getRightChildIndex(i) { return (2 * i) + 2; } getParentIndex(i) { return Math.floor((i – 1) / 2); } insert(val) { this.heap.push(val); let lastIndex = this.heap.length – 1; this.heapifyUp(lastIndex); } heapifyUp(i) { while…

🌙 Array Representation of Heap Min Heap: Insert 1 Add the element at the end. Heapify-Up from the last index. class MinHeap { constructor() { this.heap = [5, 10, 20, 30]; } getLeftChildIndex(i) { return (2 * i) + 1; } getRightChildIndex(i) { return (2 * i) + 2; } getParentIndex(i) { return Math.floor((i – 1) / 2); } insert(val) { this.heap.push(val); let lastIndex = this.heap.length – 1; this.heapifyUp(lastIndex); } heapifyUp(i) { while (i > 0) { let parentIndex = this.getParentIndex(i); if (this.heap[i] < this.heap[parentIndex]) { [this.heap[i], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[i]]; i = parentIndex; } else break; } } }…

🌙 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…