Bi-Directional Binary Search Trees?

Question

I have tried to implement a BST. As of now it only adds keys according to the BST property(Left-Lower, Right-Bigger). Though I implemented it in a different way.

This is how I think BST's are supposed to be

Single Direction BST

How I have implemented my BST

Bi-Directional BST

The question is whether or not is it the correct implementation of BST? (The way i see it in double sided BST's it would be easier to search, delete and insert)

import pdb; 
class Node:
 def __init__(self, value):
 self.value=value
 self.parent=None
 self.left_child=None
 self.right_child=None
class BST:
 def __init__(self,root=None):
 self.root=root
 def add(self,value):
 #pdb.set_trace()
 new_node=Node(value)
 self.tp=self.root 
 if self.root is not None: 
 while True:
 if self.tp.parent is None:
 break
 else:
 self.tp=self.tp.parent
 #the self.tp varible always is at the first node.
 while True:
 if new_node.value >= self.tp.value :
 if self.tp.right_child is None:
 new_node.parent=self.tp
 self.tp.right_child=new_node
 break
 elif self.tp.right_child is not None:
 self.tp=self.tp.right_child
 print("Going Down Right")
 print(new_node.value)
 elif new_node.value < self.tp.value :
 if self.tp.left_child is None:
 new_node.parent=self.tp
 self.tp.left_child=new_node
 break
 elif self.tp.left_child is not None:
 self.tp=self.tp.left_child
 print("Going Down Left")
 print(new_node.value)
 self.root=new_node
newBST=BST()
newBST.add(9)
newBST.add(10)
newBST.add(2)
newBST.add(15)
newBST.add(14)
newBST.add(1)
newBST.add(3)

Edit: I have used while loops instead of recursion. Could someone please elaborate as why using while loops instead of recursion is a bad idea in this particular case and in general?

• Blake: What do you consider the root node to be if the tree is bidirectional? Usually the root node is the node with no parents, but with bidirectional edges there can be no such nodes provided the tree has at least one edge.
• daniel: In my implementation, the root node has a parent as NULL. Same in the case of leaves. The child of all the leaves are also NULL. What I have tried to do is to keep all the connections between the Parent Nodes and their child Nodes as Bi-Directional. Though I get your point. I think, in the case which you are mentioning, the data structure would look like a circle instead of a tree. With I suppose clockwise and anticlockwise direction similar to left and right in a BST. Am i right?
• Dan D.: What you have added is what is called parent pointers. This permits one to find the next and previous item by going up and then down. Rather than starting at the top of the tree. It adds no functionality. Only changes the complexity of some operations.
• daniel: I am a little confused so as to how it will increase the complexity of operations. I think the parent pointers can be ignored fully if needs be.
• Blckknght: Having parent links could make some operations easier, as you can move up the tree more easily from a leaf node. But the benefits come with downsides, as you need to add code to update those links any time the tree structure changes. The bookkeeping work might wind up being similar to the amount of work you saved on the slightly more efficient traversals. Adding the links is not bad, it's just not a huge benefit.

Answer 1

BSTs with parent links are used occasionally.

The benefit is not that the links make it easier to search or update (they don't really), but that you can insert before or after any given node, or traverse forward or backward from that node, without having to search from the root.

It becomes convenient to use a pointer to a node to represent a position in the tree, instead of a full path, even when the tree contains duplicates, and that position remains valid as updates or deletions are performed elsewhere.

In an abstract data type, these properties make it easy, for example, to provide iterators that aren't invalidated by mutations.

Answer 2

You haven't described how you gain anything with the parent pointer. An algorithm that cares about rewinding to the parent node, will do so by crawling back up the call stack.

I've been there -- in my data structures class, I implemented my stuff with bi-directional pointers. When we got to binary trees, those pointers ceased to be useful. Proper use of recursion replaces the need to follow a link back up the tree.

• Jim Mischel: You can solve a lot of problems with "proper use of recursion," but not all of them. Consider, for example, being given a node pointer and asked to return the parent. Without parent pointers you have to traverse the tree: an O(log n) operation. With parent pointers, it's O(1). Having been there with production code, I can assure you that the difference matters.