What does an empty binary search tree look like?

Question

I am trying to write code for a binary search tree that has some basic functions. I am just having trouble with what an empty tree would look like. I know that with a linked list that there is a head that points to a nullptr. But since a binary search tree's root is an actual node, what value will be held in the root?

score 0 · Accepted Answer · answered Oct 20 '13 at 20:24

0

That depends on your tree implementation, but usually if the root itself is an empty node (e.g. nullptr) then it's an empty tree. If your root doesn't have a value even if the tree is non-empty, then look for the left and right child instead. But as said, you should know that already since it's your implementation, I guess. And if not, the type surely has an is_empty() method.

answered Oct 20 '13 at 20:24

Joey

344,408
85
689
683

So the root of my binary search tree would have the rightChild, leftChild, and data variables all pointing to nullptr if it was empty? – Suede Oct 20 '13 at 20:25
That could well be the case, yes. – Joey Oct 20 '13 at 21:09

score 0 · Answer 2 · edited May 23 '17 at 12:28

0

An empty tree is the exact same as no tree at all. see here

Programmatically spoken, the pointer itself that would generally hold the address of the trees root element is null.

edited May 23 '17 at 12:28

Community

1
1

answered Oct 20 '13 at 20:26

user2900170

75
2
5

What does an empty binary search tree look like?

2 Answers2