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:
/ \ / \
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.
- 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.
Level Order Traversal
In this, the parent is considered after both the 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 1 first, then node 3 and node 2 follows.
E.g. [3, 1, 2]
from collections import deque class Solution: def levelOrder(self, root): if not root: return None result =  depth = 0 q = deque() q.append(root) while(q): nodes = len(q) newList =  while nodes: node = q.popleft() newList.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) nodes -= 1 depth += 1 result.append(newList) return result
Now, go ahead and solve this problem: https://leetcode.com/problems/binary-tree-level-order-traversal