Binary search tree with parent is the extension of binary search tree. In binary search tree, the node has two references, left child and right child. Operations normally start from the root node. Add another reference to parent, the operations don’t have to start from root node anymore.

Binary search tree diagram

Table of Content

What is the benefit to add a parent pointer in Binary search tree?

Binary search tree diagram

When we add a reference to the parent node in the binary tree node, the operations don’t have to start from the root node. The action can start from the current node. It can go up or down the tree. The time complexity reduces from O(h) to O(1). This makes the search more efficient. However adding the parent reference need more work in insertion or deletion.


Map of binary tree implementations

Part 1 – Binary tree implementation
Part 2 – Binary search tree implementation

you are here

Part 3 – Binary search tree with parent pointer


Define classes

As its name says, the TreeNode in binary search tree with parent add one more attribute to the regular binary tree node, parent. So there are four attributes, data, left, right and parent. data is the data stored in this node. left is the reference to the left child. right is the reference to right child. parent is reference to parent node.

After we define TreeNode, we can define BinarySearchTree class. It has one attribute, root. It is the node from where most tree operations start.

Please note, since binary search tree is ordered, in Java, BinarySearchTree’s generic data type extends Comparable interface, so that we can compare data in insert, delete or search operations.

Java

JavaScript

Python


Insert

In order to insert a value to a binary search tree, we have to find the right spot. From the root, we compare the input value with each node’s data. If the value is larger than the node’s data, we move to its right child. Otherwise move to its left child, Meanwhile we keep track the previous visited node and save in variable parent.

When we reach the node whose left or right child is null, we can add the new node with the input value as left or right child. Meantime, add a reference to the parent for this new node.

Java

JavaScript

Python

Doodle

Binary search tree with parent insert


Delete by key

Delete a node in binary search tree with parent is similar to delete a node in binary search tree. First is to find the node with the data matches with the key. Then find its successor. In additional, we have to remember the parent of the deleted node, and point the successor’s parent to the old parent.

Java

JavaScript

Python


Free download

Download binary search tree with parent in Java, JavaScript and Python
Download aggregate Data Structures implementations in Java
Download aggregate Data Structures implementations in JavaScript
Download aggregate Data Structures implementations in Python