Binary Search Tree Construction [closed]

Question

Closed. This question is opinion-based. It is not currently accepting answers.

---

Want to improve this question? Because this question may lead to opinionated discussion, debate, and answers, it has been closed. You may edit the question if you feel you can improve it so that it requires answers that include facts and citations or a detailed explanation of the proposed solution. If edited, the question will be reviewed and might be reopened.

Closed 10 years ago.

Improve this question

Currently reviewing how to construct a BST, and it seems like there are two "common" ways of constructing it. One way, like this example, simply puts everything inside a Node class and does all the operation within such Node class. Another way is to break it down to both Node and BST class, and construct the tree from there.

I can see the appeal for both, but what is the standard way of constructing s BST? or is it really just more of a personal preference?

• Furqan Aziz: Recommendation is for constructing BST by using only Node class with 2 child of each node. This will be more easy to handle and only root will be there for tree.

Answer 1

There's no good reason to have a separate BST class. It doesn't have any properties that a Node doesn't also have. Any Node is also a BST.

Alternatively there is no good reason to have a Node class, just a BST class.

Whatever you call it, there's only one of it.

Answer 2

A binary tree (a binary search tree is a special case of a binary tree that satisfies a property known as binary search tree property at every node) is a recursive data structure. A binary tree is either

1. nothing (represented as null), or
2. a node with three (optionally four) things (a key, a left child and a right child).

The optional fourth part of a node can be a parent reference, which itself is a tree. This reference is useful in several useful tree operations like node deletion (and even traversal).

So, a binary tree can be sufficiently represented by a node and vice-versa and a separate BST or BinaryTree representation (for instance, as a 'class') is not needed since a binary tree can be seen as a reference to its "root" node.

Since balancing of a BST is critical for its performance, it's important to note that in practice (e.g. library code), red-black trees usually replace binary (search) trees.

With respect to this representation, a binary tree is no different from an n-ary tree.

---

There is no need to define a 'subtree' while defining a binary tree. A separate BST class is not needed because a Node is enough to represent an entire tree.

• user207421: This doesn't answer the question of whether or not to have a separate BST class. NB Either subtree can be null, but not both. The case where there are no empty subtree anywhere in the tree can only be satisfied for certain numbers of elements.
• Kedar Mhaswade: AFAIK, the definition I made is right. There is no need to define a 'subtree' while defining a binary tree. A separate BST class is not needed because a Node is enough to represent an entire tree.
• user207421: It is not correct for the reason I have already stated, which you have not addressed. It is not adequate just to reassert it in the presence of cogent objections. Your comment's second two sentences should have been posted as your answer. He wasn't asking for a definition, right or wrong, and your actual answer to the actual question should not have been deferred to a comment
• Kedar Mhaswade: This is the most meaningless comment I have come across because it is not objective at all. My definition defines correctly a binary tree without any reference to "subtree". Instead of finding a flaw in it, your comment says (paraphrasing) "Either subtree can be null, but not both".
• user207421: There is nothing either subjective or meaningless about 'either subtree can be null, but not both', and the flaw I pointed out was specifically 'can only be satisfied for certain numbers of elements'. Please explain how a binary search tree as defined by you can have three elements. Four. Five. Seven. Eight. Without having empty subtrees somewhere, i.e. a null left or right child.