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

And finally ...

Create a new file *trees.py* in your system. Open the terminal and go to folder that contains *trees.py* such that *ls* command (in Mac, Linux) or *dir* command (in Windows) should give the filename in list.

Write the following code in *trees.py* :

```
class Node:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
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
def inOrderTraversal(self, root):
def fun(root, result):
if not root:
return
fun(root.left, result)
result.append(root.val)
fun(root.right, result)
result = []
fun(root, result)
return result
def postOrderTraversal(self, root):
def fun(root, result):
if not root:
return
fun(root.left, result)
fun(root.right, result)
result.append(root.val)
result = []
fun(root, result)
return result
if __name__ == "__main__":
# main function
# create tree nodes
a = Node(val=1)
b = Node(val=2)
c = Node(val=3, left=a, right=b)
d = Node(val=6)
e = Node(val=7)
f = Node(val=5, left=d, right=e)
g = Node(val=4, left=c, right=f)
# call function of preOrderTraversal algorithm
preOrderTraversalResult = Traversal().preOrderTraversal(g)
print(preOrderTraversalResult)
# call function of inOrderTraversal algorithm
inOrderTraversalResult = Traversal().inOrderTraversal(g)
print(inOrderTraversalResult)
# call function of postOrderTraversal algorithm
postOrderTraversalResult = Traversal().postOrderTraversal(g)
print(postOrderTraversalResult)
```

Now run the file using the following command:

`python trees.py`

The result should look something like this:

```
[4, 3, 1, 2, 5, 6, 7]
[1, 3, 2, 4, 6, 5, 7]
[1, 2, 3, 6, 7, 5, 4]
```

If you get any issues while running this code/following the lab, comment below for solution.

Happy coding !!