GoHired: Binary Tree

Showing posts with label Binary Tree. Show all posts

K’th Largest Element in BST when modification to BST is not allowed

Given a Binary Search Tree (BST) and a positive integer k, find the k’th largest element in the Binary Search Tree.

      [20]
      /  \     
    [8]  [22] 
    /  \
  [5]  [10]
       /  \
     [9]  [12]

For example, in the following BST, if
if k = 3, then output should be 12
if k = 5, then output should be 9.

Mirror of Tree

Write a code to construct a Mirror of Binary Tree as below.

Find if a binary tree is height balanced ?

A Height Balanced Tree is tree where for each node this condition is true.
- The difference between heights of left subtree and right subtree for any node is not more than 1.

So we can say that a tree T is Height Balanced when
- Left Sub Tree of T is height balanced
- Right Sub Tree of T is height balanced
and for each node this above condition is true :P

Level order traversal in spiral form

Write a function to print spiral order traversal of a tree.
For below tree, function should print 1, 2, 3, 7, 6, 5, 4.

           [1]
          /   \
       [2]     [3]
      /  \     /  \ 
    [4]  [5] [6]  [7]

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Example : 00001111
Output : 4

Method 1 : in O(n) we can do it . with sequential search.

Method 2 : Binary search.
Yes binary search is useful, as data is sorted.
Just we need to change its conditions for 0 and 1.
lets have a look at Function firstOccurance.

Common Ancestor in a Binary Tree or Binary Search Tree

Binary tree with structure as

struct node {
    int data;
    struct node *left;
    struct node *right;
};

need to find out common ancestor of two nodes.

Print all nodes that are at distance k from a leaf node

Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node.

Here the meaning of distance k from a leaf means k levels higher than a leaf node.
For example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree.

           [1]
          /   \
       [2]     [3]
      /  \     /  \
    [4]  [5] [6]  [7]
    /
  [8]

Here Output should be 1, and 2 for K=2 as both are at 2 distance from leaf nodes.
1 is at K=2 distance from 5 and 2 is K=2 distance from 8.

Find min element in Sorted Rotated Array (With Duplicates)

Problem: Find the minimum element in a sorted and rotated array if duplicates are allowed:
Example: { 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 1, 1, 2} output: 0
Algorithm:

Find min element in Sorted Rotated Array (Without Duplicates)

Problem: Find the minimum element in a sorted and rotated array if duplicates not allowed:
Example: {3, 4, 5, 6, 7, 1, 2} output: 1

Check Binary Tree is Binary Search Tree or not

To search Binary Search Tree
First lets understand characteristics of BST
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.
• Each node (item in the tree) has a distinct key.

Print Vertical Sum of all the axis in the given binary Tree.

Most of times in written test , you will encounter this very good question.

given a binary tree.

(most of times a complete binary tree with all leaf node at same height will be given)

Implement a generic binary search algorithm for Integer Double String etc

A Simple Binary Search for Integers

BinarySearch(A[0..N-1], value) 
{
   low = 0
   high = N - 1
   while (low <= high) {
       mid = low + ((high - low) / 2)

Binary Tree in Java

Implementation of Binary Tree in Java Language.

import java.io.*;
import java.util.*;

class Node
   {
   public int iData;              // data item (key)
   public double dData;           // data item

GoHired