Binary Trees: Maximum Sum of nodes in Binary tree such that no two are adjacent
Problem Statement: You are given an binary tree, you need to return the sum of the nodes such that no two nodes are adjecent. It means, if we select a node, then we should not consider its children nodes in the solution. You have to consider their grand children nodes. Example In the above example, […]
Binary Trees: Find largest subtree sum in a tree
Problem Statement: Given a binary tree, you need to find the subtree with maximum sum in tree. Example Input : 1 / \ -2 3 / \ / \ 4 5 -6 2 Output : 7 Subtree with largest sum is : -2 / \ 4 5 Also, entire tree sum is also 7. Solution […]
Binary Trees: Check if a given graph is tree or not
Problem Statement: You are given an undirected graph, you need to check if the graph is a tree or not. Example In the below image, first graph is a tree, second graph is not a tree. Solution We know that an undirected graph is a tree if: 1. It has no cycle 2. If the […]
Binary Trees: Find Duplicate Subtrees
Problem Statement: You are given a binary tree, you need to find all the duplicate sub trees. Example Input : 1 / \ 2 3 / / \ 4 2 4 / 4 Output : 2 / and 4 4 Solution The solution is very simple, we need to take use of hashing and in-order […]
Binary Trees: Minimum swap required to convert binary tree to binary search tree
Problem Statement: You are given an array representation of a complete binary tree. You need to find the minimum swaps required to convert into BST. Example Consider the array: {1, 2, 3} Binary tree will be: 1 / \ 2 3 After swapping node 1 and 2, the tree will be: 2 / \ 1 […]
Binary Trees: Construct Binary Tree from preorder and inorder traversal
Problem Statement: You are given 2 arrays with inorder and pre-order. You need to construct a binary tree with the given array. Example Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] Solution We know that in pre-order traversal starts from root, goes to the left sub tree and then to right sub tree. Inorder […]
Binary Trees: Convert Binary tree into Sum tree
Problem Statement: You are given an binary tree, you need to convert into sum tree. Example Solution We can solve this problem with the help of recursion. Then we store the old value of the current node and recursively call for left and right sub tree and change the value of the current node as […]
Binary Trees: Convert Binary Tree to DLL
Problem Statement: You are given a binary tree, you need to convert into DLL. Example In-place convert Binary Tee to a Doubly Linked List 4 <-> 5 <-> 14 <-> 10 <-> 15 <-> 20 <-> 30 Solution In this solution we use in-order traversal of the tree. We perform below steps: Insert every node […]
Binary Trees: Diagonal Traversal of a Binary tree
Problem Statement: You are given a binary tree, you need to traverse diagonal and print the nodes. Example The diagonal traversal is : 10 20 30 5 15 16 4 14 Solution We shall use queue to solve the problem. We follow below steps: Enqueue root when queue is not empty, dequeue print If […]
Linked List: Segregate even and odd nodes in a Linked List
Problem Statement: You are given an LL, you need to segregate the list such that all the even number appear before all the odd numbers in the modified list. Example Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL Output: 2 -> 4 -> […]