In a binary search tree, a node has two references, left child and right child. A binary search tree with parent is an variation of a binary search tree – a node has an additional reference to its parent node. Normally a binary search tree’s operations start from the root node. With additional parent pointers, the operations can start from any given node, which improve performance.
Table of Content
Define classes
A TreeNode class in binary search tree with parent has 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. parent is the reference to the parent node.
After you define TreeNode, you can define BinarySearchTree class. It has one attribute, root.
Please note, in Java, BinarySearchTree’s generic data type extends Comparable interface. So that you can compare data in insertion, deletion and 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 |
Insert in a binary search tree with parent
In order to insert a value in a binary search tree, you have to find the right spot. From root, you compare the input value with each node’s data. If the input value is larger than the node’s data, you move to its right child. Otherwise move to its left child. You also keep track the previous visited node and save it in a variable.
When you reach a node whose left or right child is null, you can add the new node with the input value as a left or right child. Meantime, add the reference to the parent in 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 |
Delete by key
Deleting a node in a binary search tree with parent is a little more complicated. First you find the node with the data matches with the key. Then find its successor. The inorder successor in a binary search tree is the right child’s left most descendent. After you replace the deleted node with the successor, you 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 BinarySearchTreeWithParent.java
Download BinarySearchTreeWithParent.js
Download BinarySearchTreeWithParent.py
Binary tree
