Binary Tree

A binary tree is a tree represented by a pointer to the root of the tree, where each node has at most two children.

Any binary tree with $n$ nodes has a height at least $\log (n+1)-1\in \Omega (\log n)$.

Complexity Analysis

• Searching: Worse case is $O(n)$ that is when it’s a straight line.
• Insertion: Need to travel the whole tree, therefore the worse case is $O(n)$.
• Delete: Need to traverse all elements so worse case is $O(n)$.

Related

• Binary Search Tree
• Binary Heap