# Introduction to Tree Data Structure

A tree is a data structure composed of nodes connected by edges, where each node can have any data type as values. Each node in a tree can be connected to zero or more **child** nodes, depending on the type of tree, but must be connected to exactly
one **parent** node. The only exception is the **root** node, which has no parent, and every tree has only one root node. These constraints mean that a tree has no cycles or loops.

Below are some common terminologies related to trees:

**Internal node**: every node in a tree that has at least one child node.**Leaf node**: every node in a tree that has no child nodes.**Ancestor**: all the nodes that are between the path from the root to the current node are the ancestors of the current node. An ancestor node of the current node is either the parent of the current node or the parent of another ancestor of the node.**Descendent**: all the nodes that are reachable from the current node when moving down the tree are the descendants of the current node. A descendant of the current node is either a child of the node or a child of another descendant of the node.**Level**: the level of a node the number of ancestors from that node until the root node. The root node is at level 0.**Depth**: the depth of a node is the number of edges on the path from the root to that node.**Height**: the height of a node is the number of edges on the longest path from that node to a leaf. The height of a tree is the height of its root node.

## Types of Trees

### Binary Tree

An n-ary tree is a tree in which each node has no more than `n`

children. A binary tree is a type of n-nary tree with `n = 2`

, so every node in a binary tree has 0 to 2 children.

### Binary Tree implementation in Python, Java, C++ and Javascript

```
1class Node:
2 def __init__(self, val):
3 self.val = val
4 self.left = None
5 self.right = None
6
```

### Binary Search Tree

A binary search tree (BST) is a special type of binary tree, in which every nodes follows the ordering property of `all left descendents < node < all right descendents`

. Learn more about BST in Binary Search Tree Intro.

### Balanced Binary Tree

Every node in a balanced binary tree fullfills the condition--*the height difference of the left and right subtree of the node is not more than 1*. Searching, insertion, and deletion in a balanced binary tree takes `O(log n)`

instead of `O(n)`

in an unbalanced binary tree.
This is an example of a balanced binary tree:

Some common types of balanced binary trees are red-black trees and AVL trees. It's good to be aware of these trees but they are too complex to be asked in a coding interview.

## Tree Traversal

### In-order Traversal

In-order traversal visits the left branch first, then the current node, and finally the right branch. The diagram below shows the traversal order of an in-order traversal on a binary tree.

Below is a demonstration of how you would perform in-order traversal on a binary tree using recursion

### Pre-order Traversal

Pre-order traversal visits the current node first, then the left subtree, and finally the right subtree. The diagram below shows the traversal order of a pre-order traversal on a binary tree.

### Post-order Traversal

Post-order traversal visits the left subtree first, then the right subtree, and finally the current node. The diagram below shows the traversal order of a post-order traversal on a binary tree.

## How AlgoMonster encode trees

When you work through our lessons, you will encounter many problems involving trees. It is helpful to know how we encode trees, so you may be able to make up your own custom tree input to test your code.

### How AlgoMonster encode binary trees

We represent a binary tree as a string. The values of each node are separated by an empty space, and null nodes are represented by `"x"`

. The function `build_tree()`

in our driver code, which processes a given string into a binary tree, fills the tree with **pre-order traversal**.
This example demonstrates how we represent and encode a binary tree input:

The string representation of this tree is `5 4 3 x x 8 x x 6 x x`

, and this is how `build_tree()`

builds a binary tree from the string input:

### How AlgoMonster encode non-binary trees

For trees other than binary trees, we define the tree nodes as:

```
1class Node:
2 def __init__(self, val, children=None):
3 if children is None:
4 children = []
5 self.val = val
6 self.children = children
```

Similarly, we also represent a non-binary tree as a string. The values of each node and the number of its children are separated by an empty space.
The function `build_tree()`

in our driver code, which processes a given string into a tree, also fills the tree with **pre-order traversal**.
This example demonstrates how we represent and encode a non-binary tree input:

The string representation of the tree shown above is `7 3 2 1 5 0 3 0 4 0`

, and this is how `build_tree()`

builds a tree from the string input: