Problem: Find length of the subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. Example : {10, 25, 9, 30, 21, 55, 40, 60, 75} Here Length of LIS … Read More →
Root to leaf path with sum equal to given sum
Given a binary tree and a number,Write a function to find out whether there is a path from root to leaf with sum equal to given Number. In above tree, root to leaf paths exists for following sum. 7=> 1->2->4 9=> 1->3->5 10=>1->3->6 Implementation :
Check if a binary tree is subtree of another tree
Given two binary trees T1 and T2, Find whether T2 is a subtree of T1.T1 has millions of nodes and T2 has hundreds of nodes. Solution: Traverse T1 in pre-order fashion. For each node, check if the subtree rooted at this node is identical (exactly same) as T2.
Find Majority Element in an array in O(n)
The majority element is the element that occurs more than half of the size of the array. Algorithm below loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then … Read More →
Find largest BST in a binary tree
Given a Binary tree, Find largest Binary Search tree in it. A tree is a BST if: 1. Both left and right subtrees of a node are BSTs. 2. The node’s value is greater than its left subtree’s maximum value. 3. The node’s value is less than its right subtree’s minimum value. Top-Down approach : … Read More →
Heap Data Structure
Heap data structure is an array object that can be viewed as a nearly complete binary tree. Each node of the tree corresponds to an element of the array. The tree is completely filled on all levels except possibly the lowest , which is filled from the left up to a point. There are two … Read More →
Print all root to leaf paths in a tree
Given a binary tree,Print all root to leaf paths in it. root to leaf paths in above tree. [1 2 4] [1 3 5] [1 3 6] We start with the root and while traversing the tree we keep storing node data in array.We print the array when we reach a leaf node. Time Complexity … Read More →
Mysql Query – Set 4
Given an Employee table with following structure EmpId EmpName Department ManagerId Part 1: Write a sql to retrieve all Manager’s Name with 5 or more subordinates. Note : ManagerId is also an Employee Id. Part 2 : Write a sql to retrieve ManagerId who have 5 or more subordinates in one column and comma separated … Read More →
Diameter of a Tree
Definition : Diameter of a tree is the longest path between two leaf nodes in a tree. We can see in the picture below that Diameter of the tree would be maximum of these: i. Diameter of left subtree. ii. Diameter of right subtree. iii. Path that goes through the root i.e. height of left … Read More →
Replace node with sum of left and right subtree
Given a Binary tree , Replace each node with sum of values in left and right subtree. leaf nodes value will be changed to 0. Solution : i) Traverse the tree recursively. ii) Store the old value of the current node, recursively call for left and right subtrees and change the value of current node … Read More →
What’s going on ?