Binary Tree (Python)

What is a Binary tree?

A binary tree is a collection of of nodes that are linked by node with child nodes less than the node to left and nodes more than the node to the right. Just like the linked list, binary tree has a recursive definition. The leaves of a binary tree are the node that has no children and interval node are the opposite. The level of the tree is the depth of the recursion minus the head of the tree. 

Inserting node

To insert a node in a tree, first you have to compare with the current node, if the node you are about to insert is less that the current node then insert the node in the left node if not insert to the right node. If the node then equal does nothing. 

Traversing 

Traversing into the tree can be accomplished by either preorder, inorder or postorder. Preorder means to visit the parent first the children from left to right, inorder means to visit the parent in the midway and postorder is after visit the children visit the parent. 

Deleting node

There are three situations when deleting a node. Deleting a leaf, simply remove the node from there. Deleting a node with one child, remove the node and replace it with its child. Deleting a node with two children, remove the node and replace it with its in-order predecessor node, i.e. the rightmost node from the left child. 

Application

Binary tree can be useful to store an expression that is infix. Such as x + y, x * y or (x + y) * x. Binary tree can also be used to construct yes/no conditional question. Binary Tree can be efficient when its element is sorted, and the tree is balance. When the condition is fulfilled, searching in a binary tree have the same efficiency of a binary search, which it's O(log(n)). However when constructing the tree is quite slow comparing to linked list or array list. The worst is when deleting a node from the tree, it has an efficiency of O (nlogn).