1

I came across an interview question which states: How would you represent the letters A, B, C, D, E, F and G in a sorted order using a binary tree representation?

It's really stumped me. If we take G to be the root of the tree then the left child would E and the right child would be F so that the right subtree is "greater than" the left subtree. Then for the node E, its left child would be A and the right child B and F's left child would be C and its right child would be D.

Is that correct or does anyone else have a different answer?

Improve this question
1
  • You should probably look up what "sorted order" means. Hint: If G is the root, it won't have a right child. Commented Aug 25, 2015 at 0:46

3 Answers 3

Reset to default
6

The binary tree that you described is a Binary heap, which is usually used to implement priority queue.

Instead, use Binary search tree, which keeps their keys in sorted order.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

4

If you're using the letters from A to G as your complete set, the sorted binary tree would look like:

      D
  B       F  
A   C   E   G
Improve this answer

1 Comment

If you research building a complete binary tree (or binary heap) as @Yu stated, all sub-trees are full. This means that it will take log(n) time to search for what you're looking for (where n = number of nodes). As you build the tree, taking nodes from A to G as they come, D will emerge the root of the tree as this allows for all other nodes to form complete binary sub-trees.
0

Your answer to the question is incorrect. Why? When you take G as the root then all the other alphabets or keys must be on the left side of G. Meaning G will not have a right child since all nodes that form a right subtree must have greater keys than the reference key value, in this case, G.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.