Interview Question

Velocity Software Engineer Interview(Student Candidate) Kansas City, MO

Write the BST for the word "CERNER"

Answer

Interview Answer

10 Answers

2

C
  \
   E
      \
        R
      / \
    N R
   /
 E

Interview Candidate on May 21, 2012
0

are duplicates allowed in binary search tree?

Amit on Jun 18, 2012
2

No, duplicates are not allowed in binary search tree. and so the binary search tree for CERNER would be :
     C
      \
      E
        R
      / \
    N R

Anonymous on Aug 13, 2012
0

i think the answer shud bee

  c
   \
    E
     \
      R
     /
    N
   / \
  E R

sanjay on Aug 16, 2012
0

I'm not sure, but I think allowing or not allowing duplicates is just a implementation decision... both the solutions would be correct..

Anonymous on Sep 23, 2012
1

Neither a binary tree or any other tree structure allows duplicate values. The BST for CERNER would be,

          C(1)
          / \
    E(2) R(3)
  /
N(4)

The nodes in the BST will be visited in the given numerical order.

Naveen on Oct 28, 2012
3

C
           \
          E
           \
             R
           /
         N

Nikhil on Nov 5, 2012
5

Duplicates are not allowed in BST.
Also, there are more than one BST for word CERNER depending upon the root.
Importantly, Inorder traversal of BST should gives you the output in sorted order.
So, our aim is to build a BST with CENR (this should be the inorder traversal of a program)
For example: Lets consider a root as 'E'
  E
 / \
C N
      \
      R
or
  E
 / \
C R
    /
   N
I hope this helps you. :)

Sagar on Nov 12, 2012
0

Assuming a BST Tree Node is a Structure of member variables char and list(which contains the list of positions p0,p1,p2 ... Indicating the indexes of the positions of the corresponding character.)
If each reference of variable created of the Node object is named after the char it contains. The below would be the final BST

 C
     \
       E
          \
            R
           /
         N

srikanth on Apr 14, 2013
1

If you rank the letters in CERNER it will be (BST )

 c e r n e r
1 2 4 3 2 4

as BST is always complete

we add one by one to the tree

->1(C) adding C(1)

->1(C) adding E(2)
      \
       2(E)

->1(C) adding R(4)
      \
       2(E)
        \
        4(R)
re heapify

-> 2(E)
          / \
      1(C) 4(R)

-> adding N(3)

         2(E)
          / \
      1(C) 4(R)
                /
             3(N)

reheapify

         3(N)
          / \
      2(E) 4(R)
        /
     1(C)

adding e and r which are already in the tree

so the final answer would be

        N
       / \
      E R
     /
   C

Ajay on Jul 10, 2013

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up