0

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?

Community
  • 1
  • 1
user3277633
  • 1,891
  • 6
  • 28
  • 48
  • 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. – Furqan Aziz Nov 28 '15 at 01:32

2 Answers2

0

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.

user207421
  • 305,947
  • 44
  • 307
  • 483
-1

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.

Nathan Tuggy
  • 2,237
  • 27
  • 30
  • 38
Kedar Mhaswade
  • 4,535
  • 2
  • 25
  • 34
  • 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. – user207421 Nov 28 '15 at 02:54
  • 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. – Kedar Mhaswade Nov 28 '15 at 02:59
  • 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 – user207421 Nov 28 '15 at 03:06
  • 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". – Kedar Mhaswade Nov 28 '15 at 19:10
  • 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. – user207421 Nov 29 '15 at 00:25
  • Every node in a binary tree is 1) either null, or 2) a node that has three parts. I will represent these three parts as a 3-tuple (key, reference to a node -- we call it the left child, and reference to another node -- we call it the right child). Here is a binary tree with three elements: the root is (1, l2, r3), l2 is (2, null, null), r3 is (3, null, null). In this, all of the node references: root, l2, r3, *and* null satisfy the conditions specified by me. – Kedar Mhaswade Nov 29 '15 at 01:08
  • Well that's exactly what I said. Why are you arguing? Your actual answer doesn't say anything about one child being optional. And why are you misusing terms like 'meaningless' and 'subjective'? – user207421 Nov 29 '15 at 05:54
  • We are (were) both arguing. And I am going to stop doing that now. – Kedar Mhaswade Nov 30 '15 at 17:30