Category Archives: Tree

Construct Binary Tree from Postorder and Inorder Traversal

Given postorder and inorder traversal of a tree, construct the binary tree. Solution: The post order array contains the elements in the order of post order traversal of the binary tree and we know that the last element in the post order traversal is the root of the binary tree. We can then search the Read More →

Construct Tree from given Preorder and Inorder Traversals

Given preorder and inorder traversal of a tree, construct the binary tree. Solution: The pre order array contains the elements in the order of pre order traversal of the binary tree and we know that the first element in the pre order traversal is the root of the binary tree. We can then search the Read More →

Flatten A Binary Tree to Linked List (In-place)

Problem: Given a binary tree, flatten it to a linked list in-place. For example, The flattened tree should look like: Solution: We can solve this problem recursively by doing a in-order traversal of the tree. Implementation:(Recursion) Non-Recursion, No Stack We can also solve the problem even without a stack: Each time when we prune a Read More →

Check if Binary Tree is Height Balanced?

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. The solution presented is a recursive. Find the height of left and right subtrees and check the difference of Read More →

Cousin nodes in Binary Tree

Given the binary Tree and the two nodes say ‘p’ and ‘q’, determine whether the two nodes are cousins of each other or not. Solution: What are cousin nodes ? Two nodes are said to be cousins of each other if they are at same level of the Binary Tree and have different parents. For Read More →

Recursive Spiral Order Traversal of Tree

This is also called zig-zag order traversal of a binary tree. Approach: To print the nodes in spiral order, nodes at different levels should be printed in alternating order. To change the order of printing alt variable is used. If alt is 1 then printSpiralLevel() prints nodes from left to right else from right to Read More →

Recursive Level Order Traversal of a tree

Level order traversal is also called  breadth first traversal for the tree. Non-Recursive solution of the problem is – Non-recursive Level Order Traversal Approach: There are basically two functions in this method. One is to print all nodes at a given level (printLevel), and other is to get height of tree and print level wise nodes. Read More →

Print BST elements in range K1 and K2

Problem: Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1

Populate each next pointer to point to its next right node

Problem: Given a binary tree populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. You may assume that it is a perfect binary tree (i.e. all leaves are at the Read More →

Check if Two Trees are Identical

Problem: Given two binary trees, write a function to check if they are equal or not. Solution: Two binary trees are considered equal if they are structurally identical andthe nodes have the same value. Time Complexity: O(N), Where N is number of nodes in a tree. This article is contributed by Vishwas Garg. You can Read More →

Deleting all Leaves from a Binary Tree

Problem: Given a binary tree, how do you remove leaves of it? Solution: By using post-order traversal we can solve this problem (other traversals would also work). Time Complexity: O(n). Where is numbe of nodes in tree. Write or Comment if you find anything incorrect or better approach.

Spiral traversal of binary tree

binary_tree

Given a binary tree , print it’s nodes in spiral fashion. Example for Given Tree,Output should be F,B,G,I,D,A,C,E,H This is also called zig zag tree traversal. Algorithm : We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal Read More →