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 →
Frequency of a given number in a Linked List
You are given a linked list. You have to write a function that will give frequency of a given number in linked list. Here is a solution Algorithm: 1. Initialize count as zero. 2. Loop through each element of linked list: 3. If element data is equal to the given number then increment the count. … Read More →
Check for Children Sum Property in a Binary Tree
You are given a binary tree, you have to check if tree satisfies the property of children sum. This property says that for each node sum of its left and right children should be equal to node value. Solution: 1)Traverse the given binary tree (recursively) 2) For each node check if the node and both … Read More →
Inorder Predecessor in Binary Search Tree
In Previous Post We learned about In-Order Successor.In this post ,We’ll learn what is In-Order Predecessor. The predecessor of a node x in a search tree is the node with largest key that belongs to the tree and that is strictly less than x’s key. In above binary search tree, in-order predecessor of 17 is … Read More →
Inorder Successor in Binary Search Tree
Given a node in binary search tree say x,the in-order successor of node x is the node with the smallest value greater than node x’s value. In above binary search tree, in-order successor of 18 is 20, successor of 6 is 7 and successor of 13 is 15. Algorithm : In in-order traversal of binary … Read More →
Copy a linked list with next and arbit pointer
Problem: Given a doubly linked list with one pointer of each node pointing to the next node just like in a singly linked list. The second pointer(arbit pointer) however can point to any node in the list and not just the previous node. Write a program in to create a copy of this list. Algorithm: … Read More →
Find Union and Intersection of 2 sorted arrays
Union refers to the set of all the elements of the 2 arrays. Intersection here refers to the set of elements which are common in both the arrays. Steps to find union of 2 arrays: 1) i and j, initial values i = 0, j = 0 2) If a1[i] < a2[j] then print a1[i] … Read More →
Print all ancestors of a node in binary tree
Problem: Given a Binary tree and a node’s value, Write a function to print all the ancestors of the node. Thinking of solution??Think Recursively.This problem can be easily solved using recursion. We start from the root of the tree and keep going down the tree. When we reach the node with given value we return … Read More →
Rotate linked list by K nodes
You are given a singly linked list, rotate the linked list counter-clockwise by k nodes. Where k is a given positive integer. i.e. if the given linked list is: 1->2->3->4->5 and k is 3, the list should be modified to: 4->5->1->2->3. Assume that k is smaller than the number of nodes in linked list. Steps: … Read More →
Find the smallest positive number missing from an unsorted array
You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space. Example: Input = {2, 3, 4, 6, 8, -1, -3} Output = 1 Input = { 1, 3, -7, 6, 8, 1, -5, 5 … Read More →
Sort an array of 0s,1s,2s
You are given an array of 0s 1s and 2s in random order. Sort the array so the o,1 and 2 are segregated. This problem is similar to Dutch national Flag problem. Method 1: Use count sort logic. Complexity: O(N) Method 2: 1. Sort the array treating {0} as one group and {1, 2} … Read More →
Lowest common ancestor in a Binary Tree.
Problem : Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Lowest Common Ancestor: The lowest common ancestor (LCA) of two nodes v and w is defined as the lowest node in tree that has both v and w as descendants (where we allow a node to be … Read More →
What’s going on ?