A binary tree is a tree where each node has at most two children.
In a binary tree, each parent node's children are pointers to
In the example binary tree above, the node with
6has two child nodes:
leftchild node is
rightchild node is
Binary Tree Traversal
Using the same example binary tree, let's go over the 3 ways to traverse a binary tree:
- In order traversal visits nodes in the order left, root, and right:
-4, 6, 7, 9, 1, 8
- Pre order traversal visits nodes in the order root, left, and right:
9, 6, -4, 7, 1, 8
- Post order traversal visits nodes in the order left, right, and root:
-4, 7, 6, 8, 1, 9
Binary Tree Big O
The leaves in a binary tree are the last nodes that can be traversed to from the root that have no children nodes
hthat represents the height of the tree, or the distance between the root and the leaf node, the time complexity of traversing to a leaf node is
Binary Search Tree
A binary search tree (BST) is a binary tree of sortable elements that satisfies the following criteria:
- All elements on the left subtree are less than the parent node.
- All elements on the right subtree are greater than the parent node. BSTs that allow duplicates are often included as part of the tree's definition. For example, the values on the right are greater than or equal to the parent node.
Searching for elements in a binary search tree generally takes
O(h)if the tree is relatively balanced, and
O(n)in the worst case.