Binary trees

• A binary tree is a tree in which no node can have more than two children.
• A property of a binary tree that is sometimes important is that the depth of an average binary tree is considerably smaller than N
• The average depth of a Binary Tree is $O( \sqrt N)$
• The average depth of a binary search tree is O(log n)
• This general strategy (left, node, right) is known as an inorder traversal
• An alternate traversal strategy is to recursively print out the left subtree, the right subtree, and then the root. This traversal strategy is generally known as a postorder traversal.
• A third traversal strategy is to print out the root first and then recursively print out the left and right subtrees. This is known as a preorder traversal