# Binary Tree

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

`left`

and `right`

nodes.In the example binary tree above, the node with

`6`

has two child nodes:- The
`left`

child node is`-4`

. - The
`right`

child node is`7`

.

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

`h`

that 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`O(h)`

.## 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.## 9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.

- 1.Inorder TraversalEasy
- 2.Tree SumEasy
- 3.Tree HeightEasy
- 4.LCAMedium
- 5.Max Path SumHard
- 6.Search mazeMedium
- 7.Number of islandsMedium
- 8.Kth SmallestMedium
- 9.Sort K ArraysHard