Given a BST with 2 nodes swapped, fix it
Posted on September 4, 2015
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Problem Given a BST with 2 nodes swapped fix it.
Example
Consider the BST:
Following is the correct BST 10 / \\ 5 20 / \\ 2 8 Now we swap 8 and 20, and BST is changed.
Input Tree: 10 / \\ 5 8 / \\ 2 20 In the above tree, nodes 20 and 8 must be swapped to fix the tree. ```In the [previous post](http://k2code.blogspot.in/2015/09/given-binary-search-tree-with-2-nodes.html), we saw how many pairs in the input tree violate the BST property.
[Read More]Given a binary search tree with 2 nodes swapped find number of pairs not following BST properties
Posted on September 4, 2015
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem Given a binary search tree with 2 nodes swapped, give the number of nodes not following bst property. Follow up - Fix the BST, in the next post.
Example
Consider the BST:
Following is the correct BST 10 / \\ 5 20 / \\ 2 8 Now we swap 8 and 20, and BST is changed.
Input Tree: 10 / \\ 5 8 / \\ 2 20 In the above tree, nodes 20 and 8 must be swapped to fix the tree.
[Read More]Given the post order array find if tree is BST
Posted on June 25, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem An array which is a Post order traversal of a Binary Tree. Write a function to check if the Binary Tree formed from the array is a Binary Search Tree.
Eg:
2
1 3
The array given as input would be 1 3 2.
Write a function to say if the tree formed is a Binary Search Tree.
Example 2: 4 is root. 0 is left child of 1 , 1 is left child of 2 and 2 is left child of 4.
[Read More]Sorted Linked List to Balanced BST
Posted on February 26, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem : Given a Singly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Linked List.
**Example : **
Input: Linked List 1->2->3->4->5->6->7 Output: A Balanced BST 4 / \\ 2 6 / \\ / \\ 1 3 4 7 Lets discuss 2 approaches for this problem.
Solution
Method 1 (Simple)
Following is a simple algorithm where we first find the middle node of list and make it root of the tree to be constructed.
[Read More]Convert sorted array to Balanced BST
Posted on February 26, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.
Examples
Input: 1 2 3 4 5 6 7 Output: 4 / \\ 3 6 / \\ / \\ 3 4 6 7 Solutions ** Method 1 - Take the array’s middle element and insert it recursively**
Pick up the middle element of the array Set it as the root Recursively build up left and right subtrees with lower and higher halves of the array Here is the code in java:
[Read More]Create linked lists of all the nodes at each depth for a BST
Posted on February 10, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)
Example
So a binary tree such as :
(1) / \\ / \\ (2) (3) / \\ / \\ (4) (5) (6) (7) Will return linked lists:
(1) => NULL (2) => (3) => NULL (4) => (5) => (6) => (7) => NULL Solution
[Read More]Binary Tree Level-Order Traversal Using Depth First Search (DFS) [Not to USE BFS]
Posted on October 5, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level. Breadth First Search (BFS) is not allowed. We have already seen how to do level order traversal here.
Example
So consider the tree:
1
/ \
2 3
/ \ / \
4 5 6 7
The BFS or level order traversal here is :
[Read More]Binary Tree Post-Order Traversal - Recursive and Iterative Solution
Posted on October 5, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Consider the tree:
To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.
Therefore, the Postorder traversal of the above tree will outputs:
[Read More]Find the rank w.r.t K - Number of nodes with value less than K
Posted on October 5, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
If the rank of the BST is k, it implies how many nodes/keys are less than k.
So, it boils down to 3 easy recursive calls
In the simplest case if K==node value, then whole of the let is rank of the node if K < node.value then we know that rank depends on the size of left sub tree and its less than sub tree’s length If K > node.
[Read More]Balanced Binary Search Tree Index
Posted on August 25, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra