The binary search tree with parent is the extension of the binary search tree. In a binary search tree, the node has two references, the left child and the right child. Operations normally start from the root node. Add another reference to the parent, the operations don’t have to start from the root node anymore.
Table of Content
What is the benefit of adding a parent pointer in a node of a binary tree?
Normally a binary tree’s operation starts from the root. If you add a parent pointer in a node, The action can start from the current node. It can go up or down the tree. This makes the search more efficient. However, adding the parent reference needs more work in insertion or deletion.
Map of binary tree implementations
Part 1 – Binary tree implementation
Part 2 – Binary search tree implementation
Part 3 – Binary search tree with parent pointer
Define classes
As its name says, the TreeNode in binary search tree with parent adds 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 the right child. The parent is a reference to the parent node.
After we define TreeNode, we can define the BinarySearchTree class. It has one attribute, root. It is the node from where most tree operations start.
Please note, since a binary search tree is ordered, in Java, BinarySearchTree’s generic data type extends the Comparable interface, so that we can compare data in insert, delete, or search operations.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public class BinarySearchTreeWithParent<T extends Comparable<T>> { //TreeNode with a parent reference static class TreeNode<T> { T data; TreeNode<T> left = null; TreeNode<T> right = null; TreeNode<T> parent = null; //Override, Time O(1), Space O(1) @Override public String toString() { return String.valueOf(data); } } TreeNode<T> root = null; } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class TreeNode { //Constructor, with parent pointer, Time O(1), Space O(1) TreeNode() { this.left = null; this.right = null; this.parent = null; } //Override, Time O(1), Space O(1) toString() { return this.data; } } class BinarySearchTreeWithParent { //Constructor, Time O(1), Space O(1) constructor() { this.root = null; } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class TreeNode : #Constructor, TreeNode with a parent reference, Time O(1) Space O(1) def __init__(self) : self.left = None self.right = None self.parent = None; #Override, Time O(1), Space O(1) def __str__(self): return str(self.data) class BinarySearchTreeWithParent : #Constructor, Time O(1) Space O(1) def __init__(self) : self.root = None |
Binary search tree with parent method – Insert
To insert a value into 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 of the previously visited node and save it in a 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. Then, add a reference to the parent for this new node.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//Insert with parent pointer, Iteration, Time O(h) Space O(1), h is height of tree public void insert(T value) { TreeNode<T> newNode = new TreeNode<>(); newNode.data = value; if(root == null) { root = newNode; return; } TreeNode<T> curr = root; TreeNode<T> parent; while(true) { parent = curr; if(value.compareTo(curr.data) < 0) { curr = curr.left; if(curr == null) { parent.left = newNode; newNode.parent = parent; return; } } else { curr = curr.right; if(curr == null) { parent.right = newNode; newNode.parent =parent; return; } } } } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//Insert with parent pointer, Iteration, Time O(h) Space O(1), h is height of tree insert(value) { var newNode = new TreeNode(); newNode.data = value; if(this.root == null) { this.root = newNode; return; } var curr = this.root; var parent; while(true) { parent = curr; if(value < curr.data) { curr = curr.left; if(curr == null) { parent.left = newNode; newNode.parent =parent; return; } } else { curr = curr.right; if(curr == null) { parent.right = newNode; newNode.parent =parent; return; } } } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#Insert with parent pointer, Iteration, Time O(h) Space O(1), h is height of tree def insert(self, value) : newNode = TreeNode() newNode.data = value if self.root == None : self.root = newNode return curr = self.root parent = None while True : parent = curr if value < curr.data: curr = curr.left if curr == None: parent.left = newNode newNode.parent = parent return else : curr = curr.right if curr == None: parent.right = newNode newNode.parent =parent return |
Doodle
Delete by key
Deleting a node in a binary search tree with a parent is similar to deleting a node in a binary search tree. The first thing is to find the node with the data that matches the key. Then find its successor. In addition, we have to remember the parent of the deleted node and point the successor’s parent to the old parent.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
//Delete with parent pointer, Iteration, Time O(h) Space O(1) public TreeNode<T> delete(T key) { if (root == null ) return null; if (root.data == key){ //delete root root = deleteNode(root); //reset the root root.parent = null; return root; } TreeNode<T> curr = root; while (true) { if (key.compareTo(curr.data) > 0) { if (curr.right == null ) break; else if (curr.right.data == key) { TreeNode<T> oldParent = curr.right.parent; curr.right = deleteNode(curr.right); if (curr.right != null) curr.right.parent = oldParent; break; } curr = curr.right; } else { if (curr.left == null) break; else if (curr.left.data == key) { TreeNode<T> oldParent = curr.right.parent; curr.left = deleteNode(curr.left); if (curr.left != null) curr.left.parent = oldParent; break; } curr = curr.left; } } return root; } //Delete node, Time O(h), Space O(1) private TreeNode<T> deleteNode(TreeNode<T> node) { if (node == null) return null; if (node.right == null) return node.left; TreeNode<T> curr = node.right; while (curr.left != null) //find the left-most node curr = curr.left; curr.left = node.left; // put the original left under left most, if (node.left!=null) node.left.parent = curr; // link the new far left part to old far left return node.right; } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
//Delete with parent pointer, Iteration, Time O(h) Space O(1) delete(key) { if (this.root == null ) return null; if (this.root.data == key){ //delete root this.root = this.deleteNode(this.root); //reset the root this.root.parent = null; return this.root; } var curr = this.root; while (true) { if (key > curr.data) { if (curr.right == null ) break; else if (curr.right.data == key) { let oldParent = curr.right.parent; curr.right = this.deleteNode(curr.right); if (curr.right != null) curr.right.parent = oldParent; break; } curr = curr.right; } else { if (curr.left == null) break; else if (curr.left.data == key) { let oldParent = curr.right.parent; curr.left = this.deleteNode(curr.left); if (curr.left != null) curr.left.parent = oldParent; break; } curr = curr.left; } } return this.root; } //Delete node, Time O(h), Space O(1) deleteNode(node) { if (node == null) return null; if (node.right == null) return node.left; var curr = node.right; while (curr.left != null) //find the left-most node curr = curr.left; curr.left = node.left; // put the original left under left most, if (node.left != null) node.left.parent = curr; // link the new far left part to old far left return node.right; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#Delete with parent pointer, Iteration, Time O(h) Space O(1) def delete(self, key) : if self.root == None : return None if self.root.data == key: #delete root self.root = self.deleteNode(self.root) #reset the root self.root.parent = None return self.root curr = self.root while True : if key > curr.data : if curr.right == None : break elif curr.right.data == key: oldParent = curr.right.parent curr.right = self.deleteNode(curr.right) if curr.right != None: curr.right.parent = oldParent break curr = curr.right else : if curr.left == None: break elif curr.left.data == key : oldParent = curr.right.parent curr.left = self.deleteNode(curr.left) if curr.left != None: curr.left.parent = oldParent break curr = curr.left return self.root #Delete node, Time O(h), Space O(1) def deleteNode(self, node) : if node == None: return None if node.right == None: return node.left curr = node.right while curr.left != None: #find the left-most node curr = curr.left curr.left = node.left # put the original left under left most, if node.left != None: node.left.parent = curr # link the new far left part to old far left return node.right |
Free download
Download binary search tree with parent in Java, JavaScript and Python
Data structures introduction PDF