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

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

### 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. root is at the node at the top of the tree. It is the node from where most tree operations start.

## Python

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

## Doodle 2

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

## Doodle

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

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

## Doodle

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

## Doodle

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

## Doodle

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