Quickstart Trees on LeetCode

trees dsalgo leetcode cp

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

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

Discussion

1