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

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 !!

Discussion