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.
Swap every two nodes in a linked list
Given a singly linked list, swap every two nodes e.g. 1->2->3->4->5->6 should become 2->1->4->3->6->5 Solution: This can be done using two pointers. Take a current and temp pointer. At each iteration swap temp and current node. Repeat the steps until null node. You can think of the recursive solution of the problem. Implementation:
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 →
Find first non repeating character in a string
You are given a string, find its first non-repeating character? Algorithm: 1) Scan the string from left to right and construct the count array. 2) Again, scan the string from left to right and check for count of each character, if you find an element who’s count is 1, return it. Time complexity: O(N)
Find local minima in an array
You are given an array Arr[1 .. n] with the special property that Arr[1] ≥ Arr[2] and Arr[n − 1] ≤ Arr[n]. We say that an element Arr[x] is a local minimum if it is less than or equal to both its neighbors. Derive an algorithm in O(log n) For example in the array 9,6,2,14,5,7,4 … Read More →
Binary Tree diff of sum of nodes at odd and sum of nodes at even
Given a Binary Tree, write a function which calculates the difference between the sum of node values at odd levels and sum of node values at even levels. Consider the root node is at height 1. The solution is short and uses recursion. The idea is that you negate all levels under the current one … Read More →
Even numbers at even index and Odd numbers at odd index
You are given an array of positive numbers. You have to rearrange array such that even numbers at even position and odd numbers at odd positions. If suppose odd numbers exceeds the even numbers or vice-versa than keep them untouched. Do this in one pass and without using any extra memory. input : {2 5 7 … 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 →
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 →
Delete alternate nodes of a Linked List
You are given a Singly Linked List. Starting from the second node delete all alternate nodes of it. For example, if the given linked list is 1->4->8->10->15 then your function should convert it to 1->8->15 Solution: Steps: Take two pointers p and q Initially p points to head and q points to link of p … Read More →
What’s going on ?