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

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 a particular order. The time complexity of most binary tree operations is O(n) in the worst case.

### 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

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

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

## Python

### Add child

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.

## Doodle

### Delete by key

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

Since a 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 rightmost child of the left child. On the other hand, to promote the right child as a successor, the left child of the deleted node will be linked to the leftmost 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.

To search all nodes of the tree for the key, we use recursion. In the recursion wrapper method, check the key with the 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 a leaf, has one child, or has two children. Then call itself with left or right child node.

## Doodle 2

### Depth first search (DFS)

There are two ways of searching: 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.

## Python

### Breadth first search (BFS)

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.

## Doodle

### Inorder traversal

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

For depth-first search, there are three ways: inorder, preorder, and postorder. They can be implemented using recursion and stack. In this post, we use recursion to implement DFS.

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

## Doodle

### Preorder traversal

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

## Doodle

### Postorder traversal

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

## Doodle

### Levelorder traversal

On the other hand, breadth-first search uses levelorder. It is to traverse nodes level by level. The level of a particular node refers to how many generations the node is from the root. We use a queue to implement BFS.

## Doodle

### How to implement a binary tree?

First, define a TreeNode class. It has one data attribute and two references to two child nodes. Then you can start to build a binary tree by connecting one node as another node’s child.