A tree is a hierarchical data structure. It consists of nodes with a root node at the top and subtree of children nodes. The nodes are connected by edges. Each parent node can point to null, one or multiple nodes.

A binary tree has at most two children, we name them left child and right child. Each node has a value associated with it. They are not in particular order. The time complexity of most binary tree operations is O(n) in the worst case.

binary tree diagram

Table of Content


Define classes

Tree consists of nodes. The first thing is to define the TreeNode. It has three attributes, data, left, right. data is the data stored in this node. Its data type can be anything such as Integer, String or objects. left is the left child. right is the right child. Their data type is TreeNode.

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

Java

Javascript

Python


Add

Since all the nodes in the binary tree are not ordered in any way, we can add the left and right child directly to any node. If there are children for this node already, this method simply replaces the children with new ones.

Java

Javascript

Python

Doodle

Binary Tree add node


Delete by key

Delete node is the most complicated operation in the tree. Because we have to find the node which matches with key, and find the successor so that the parent of deleted node can connect to its successor.

Since binary tree is not ordered, there are two cases to consider the successor, either promote the left child as the replacement, or promote the right child to be the replacement.

To promote the left child as successor, the right child of the deleted node will be linked to the right most child of the left child. On the other hand, to promote the right child as successor, the left child of the deleted node will be linked to the left most child of the right child. Two methods are created to deal with different cases. You can select which one to use based on your design.

In order to search all nodes of the tree for the key, we use recursion. In the recursion wrapper method, check the key with root’s data . If matched, we have to reset the root to point to its successor. In the recursion helper method, check the cases such as whether the node is leaf, has one child, or have two children. Then call itself with left or right child node.

Java

Javascript

Python

Doodle 1

Binary Tree delete node left child successor

Doodle 2

Binary Tree delete node right child successor


Search by key

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.

Java

Javascript

Python

Doodle

Binary Tree search bfs


Traversal

Traversal is to visit all nodes in the tree, either print or save their values to an output list. Similar to search, we can use depth first search or breadth first search.

For depth first search, there are three ways: inorder, preorder and postorder. In this post, we use recursion to implement DFS.

  1. Inorder is to traverse the left subtree, visit the root, traverse the right subtree.

Java

Javascript

Python

Doodle

Binary Tree inorder


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

Java

JavaScript

Python

Doodle

Binary Tree preorder


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

Java

JavaScript

Python

Doodle

Binary Tree postorder

For breadth first search, we call it Level order. It is to traverse the nodes level by level. We use queue to implement.

Java

Javascript

Python

Doodle

Binary Tree level order

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