Quickstart Trees on LeetCode

This is a beginner lab and primer to start solving questions on trees in Data Structures and Algorithms.

**What is a tree?**

A tree is a data structure that looks like this:

4️⃣

/ \

3️⃣ 5️⃣

/ \ / \

1️⃣ 2️⃣ 6️⃣ 7️⃣

**Why does it look like this?**

In the above representation, it is what we call a tree and each point holding a value is called a node. A node is classified depending on it's placement in the structure.

Node with value 4 --> called root node coz it has no parent above it

Node with value 3 --> is left child of root node, sibling of node with value 5 and parent node of nodes with value 1 and 2.

Node with value 1 --> is left child of node with value 3, sibling of node with value 2 and also called leaf node as it doesn't have any children.

Node with value 2 --> is right child of node with value 3, sibling of node with value 1 and also called leaf node as it doesn't have any children.

Node with value 5 --> is right child of root node, sibling of node with value 3 and parent node of nodes with value 6 and 7.

Node with value 6 --> is left child of node with value 5, sibling of node with value 7 and also called leaf node as it doesn't have any children.

Node with value 7 --> is right child of node with value 5, sibling of node with value 7 and also called leaf node as it doesn't have any children.

Let's summarize!

We have

- four leaf nodes -> 1, 2, 6, 7
- three parent nodes -> 4, 3, 5
- one root node -> 4
- one tree -> type binary as there are maximum two children nodes of parent nodes

**Why do we need to traverse?**

- To find out tree node value
- To make calculations on the basis of tree node value

**How to define node using code? (naiice, it rhymes :p)**

```
class Node:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
```

**What are the algorithms to traverse trees?**

There are many but we will look at three ways to walk through a tree.

- Pre-order
- In-order
- Post-order
- Level-order

Pre-order Traversal

It is named so, because the parent is considered before left child and right child. Let's say, a tree with node 3 has children node 1 and node 2. Then, in this traversal, we will print node 3 first, then node 1 and node 2 follows.

E.g. [3, 1, 2]

```
class Traversal:
def preOrderTraversal(self, root):
def fun(root, result):
if not root:
return
result.append(root.val)
fun(root.left, result)
fun(root.right, result)
result = []
fun(root, result)
return result
```

Now, go ahead and solve this problem: https://leetcode.com/problems/binary-tree-preorder-traversal