In tree, nodes often represent entities or objects. The lines (edges) between the nodes represent the way the nodes are related. Edges are likely to be represented by reference. Generally we are restricted to going in one direction along edges, from the root downward.

Binary search tree diagram

But sometimes, we add a reference to the parent node so that it will be more efficient for some operations such as find inorder successor in binary search tree. With the help of parent pointer, the action starts from the current node instead of root node. The time complexity reduces from O(h) to O(1). But for other operations, such as insert or delete, there will be more work. we have to add or remove reference to the parent for each node.

you are here

Part 1 – Binary tree implementation
Part 2 – Binary search tree implementation
Part 3 – Binary search tree with parent pointer

Table of Content

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.





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.





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.




Search by key

Search in binary search tree with parent is the same as search in binary search tree. There are two ways to search, Depth first search and Breadth first search.

Depth first search (DFS) starts from the root, and explores the child nodes as far as possible before backtracking. DFS is usually implemented with recursion or stack.

Breath First Search (BFS) starts from the root, and explores all its children before going to the next level. BFS is usually implemented with Queue.

Please refer to search in binary search tree for implementation.


The traversal is to visit all nodes in the tree. It is the same as binary tree, including inorder, preorder, postorder and level order.

Inorder is to traverse the left subtree, visit the root, traverse the right subtree. In binary search tree, the output of the key should be in ascending order.

Preorder is to visit the root, traverse the left subtree, traverse the right subtree.

Postorder is to traverse the left subtree, traverse the right subtree, visit the root.

Level order is to traverse the nodes level by level. 

please refer to the traversal of binary tree for the implementation.

Download Java, JavaScript and Python code
Binary tree animated visual
Data structures and Java collections