Preorder Traversal in a Binary Tree (With C Code)

Summary

In this video, the speaker provides an in-depth explanation of preorder traversal in binary trees. Starting with a basic introduction to tree traversals, the speaker explains how preorder traversal works by visiting the root node first, followed by the left subtree, and then the right subtree. Using a sample tree, the process is demonstrated step by step. Additionally, a recursive function for preorder traversal in C programming is explained. The speaker highlights how recursion simplifies traversal tasks and concludes with a demonstration of the code in action, emphasizing its simplicity.

Takeaways

• 🌳 Preorder traversal is a method for traversing a tree data structure.
• 📝 The mnemonic for remembering the order of traversal is 'Left-Right-Root' for preorder.
• 🔑 The key steps in preorder traversal are: visit the root node first, then the left subtree, and finally the right subtree.
• 👨‍🏫 The video uses a visual example of a tree to demonstrate how preorder traversal is performed.
• 📑 The script explains a technique to remember the order of traversal by writing 'Root', 'Left', and 'Right' in their respective order.
• 💡 The script emphasizes the importance of understanding the difference between preorder, inorder, and postorder traversals.
• 🛠️ Recursion is used in the code to implement the preorder traversal function, simplifying the process.
• 💻 The script provides a pseudo code example for the preorder traversal function, highlighting the simplicity of the approach.
• 🔍 Preorder traversal can be used for searching or processing all nodes in a tree, as it visits every node.
• 📈 The video script includes a step-by-step guide on how to code the preorder traversal function in a programming language.

Q & A

What is preorder traversal in a binary tree?

Preorder traversal is a tree traversal method where the root node is visited first, followed by the left subtree and then the right subtree. The sequence is Root, Left, Right.

How can you remember the order of preorder traversal?

A simple way to remember the order is to write the word 'Root' first, followed by 'Left' and 'Right'. This reminds you that in preorder traversal, you visit the root node first, then the left subtree, and finally the right subtree.

What would the preorder traversal be for the tree given in the script?

The preorder traversal for the given tree is 4, 1, 5, 2, 6.

What happens if the root node is NULL in the traversal function?

If the root node is NULL, it means that either the tree is empty or you have reached a leaf node. In this case, the traversal function does nothing and simply returns.

Why is recursion commonly used for preorder traversal?

Recursion is used because the preorder traversal problem is naturally recursive. For each node, you visit the root, then recursively visit the left subtree, and finally the right subtree. Recursion simplifies the implementation of this process.

How is the 'preorder' function implemented in code?

The 'preorder' function checks if the root is NULL. If it is not, the function prints the root's data and then recursively calls itself for the left and right children of the root.

What is the structure of a tree node as mentioned in the script?

A tree node is represented as a 'struct node', which contains data and pointers to the left and right child nodes.

What are the basic elements inside a tree node?

Each tree node contains three elements: data (the value stored in the node), a left pointer (to the left child), and a right pointer (to the right child).

How is the preorder traversal output presented in the script?

The preorder traversal output is presented as '4, 1, 5, 2, 6'. The presenter humorously refers to this sequence as the 'phone number' of the tree.

Why is it important to understand tree traversal in data structures?

Tree traversal is crucial in data structures because it allows you to visit every node in a structured manner, which is essential for tasks like searching, inserting, or performing operations on each node.

Outlines

00:00

🌳 Understanding Preorder Traversal in Trees

In this section, the speaker introduces the concept of preorder traversal in trees, building on previous discussions about tree traversals. They explain how to perform preorder traversal by visiting the root node first, followed by the left and right subtrees. The speaker emphasizes the importance of remembering traversal orders by using mnemonics and guides the audience through an example tree. They explain how to mark subtrees and recursively apply preorder traversal to different parts of the tree.

05:00

💻 Writing the Preorder Traversal Function

This paragraph delves into the coding part of preorder traversal. The speaker walks through writing a simple C function to implement the traversal. They describe the structure of the `struct node` used to represent a tree node, explain the base case for the recursive function (when the root is null), and outline the process for printing the root node’s data. The speaker points out that recursive calls are made to traverse the left and right children, using pseudo code and addressing potential coding mistakes, such as missing semicolons, when transitioning to an actual code editor.

10:01

🚀 Running the Preorder Traversal Code

The final paragraph covers testing the preorder traversal function. The speaker runs the function on a predefined tree (4, 1, 6, 5, 2) and verifies the output matches the expected preorder sequence (4, 1, 5, 2, 6). They emphasize the simplicity and effectiveness of recursion in solving traversal problems. The section concludes with a reminder for viewers to follow the complete Data Structures and Algorithms playlist, especially for those who may have missed earlier videos.

Keywords

💡Preorder Traversal

Preorder traversal is a tree traversal method where the root node is visited first, followed by the left subtree, and then the right subtree. In the video, it is explained as 'Root, Left, Right,' and the presenter shows how this order is applied in practice using an example tree with the nodes 4, 1, 5, 2, and 6.

💡Root Node

The root node is the topmost node in a tree data structure, from which all other nodes descend. In the context of the video, the root node is the first node to be visited during preorder traversal. For the example tree, node 4 is the root.

💡Subtree

A subtree is a portion of a tree that includes a node and all of its descendants. In the video, the presenter refers to 'subtree 1' and 'subtree 2' to break down the preorder traversal process and shows how each subtree is visited in turn.

💡Tree Traversal

Tree traversal refers to the process of visiting all the nodes in a tree data structure in a specific order. The video covers one such method, preorder traversal, but also briefly mentions other traversal methods like inorder and postorder, each with a different node visitation order.

💡Recursive Function

A recursive function is a function that calls itself to solve a problem by breaking it down into smaller instances. In the video, the preorder traversal function is implemented recursively, allowing the function to call itself on the left and right subtrees of the current root node.

💡Data Structure

A data structure is a way of organizing and storing data to enable efficient access and modification. The video focuses on the tree data structure, demonstrating how tree traversal can be used to visit all nodes. Specifically, it shows how preorder traversal is performed on a binary tree.

💡Struct Node

A struct node in programming is a data structure that holds information, typically including pointers to other nodes (left and right children) and data values. In the video, the presenter explains how a struct node is defined in the context of a binary tree, containing the node's data and its left and right pointers.

💡Null Check

A null check ensures that a pointer or reference is not pointing to null (i.e., no valid data) before accessing it. In the video, the preorder traversal function checks if the root is null before proceeding, ensuring that it does not attempt to traverse an empty tree or reach beyond the leaf nodes.

💡Pseudo Code

Pseudo code is a simplified, informal way of writing a program's logic without focusing on syntax specific to any programming language. In the video, the presenter writes pseudo code to explain the logic of preorder traversal, using it as a teaching tool before implementing the actual code.

💡Binary Tree

A binary tree is a type of tree data structure where each node has at most two children, referred to as the left and right child. The video presents an example of a binary tree with nodes 4, 1, 5, 2, and 6, and walks through how preorder traversal works on this structure.

Highlights

Introduction to preorder traversal, a type of tree traversal method.

Recap of the previous video, which provided an overview of tree traversals and why they are done.

Step-by-step explanation of how to perform preorder traversal on a sample tree.

Reminder: Root, Left, Right is the order in preorder traversal.

Tip to remember different traversals: Write 'Root' for preorder, 'Root' at the end for postorder, and 'Root' in between for inorder.

Starting preorder traversal from the root node of the tree.

Breakdown of the traversal process: visit the root first, then the left subtree, followed by the right subtree.

Illustration of how to solve a subtree and mark nodes during the traversal process.

Practical example: The preorder traversal result for a tree with nodes 4, 1, 5, 2, 6.

Explanation of a recursive function to perform preorder traversal in code.

Introduction to struct node in C, used to represent tree nodes.

Pseudo-code demonstration for preorder traversal with basic conditional logic.

Clarification of the use of recursion to simplify tree traversal problems.

Coding example of preorder traversal: showing how to print nodes in the correct order.

Conclusion: Encouragement to review the playlist for a comprehensive understanding of Data Structures and Algorithms.

Transcripts

In today's video

we are going to look at the preorder traversal thoroughly.

In the last video, I had given you a very good idea of ​​traversals

That why these tree traversals are done.

And today we'll take a closer look at the preorder traversal

And this tree which I have just made for you people

I will show you as an example

that how to do preorder traversal

So, the tree you see, we are going to do preorder traversal in it

So, what is preorder traversal called, right?

I told you people

Sometimes you forget that what is pre,

what is post,

and what is in order

So, what should you do

First you write

You write left in left,

write left in left,

you write right in right

Okay

Wrote right on the right side, left written on the left side

If it is pre then write the Root here

Ok, if there was a post then I would write the Root here

And if these were (in)

then the Root would be written inside these two,

i.e., write (in) here, Ok

That's a way of remembering, OK

Root, Left or Right this is our preorder traversal

That you first visit the root node

After that you guys visit the left subtree

then visit the right subtree, OK

So, there is Root, after that Left and after that Right

This is our preorder traversal, Ok

So, this is our preorder traversal

In this, if I talk about what I will do first

I will visit the root, the root node of this tree

So, I will visit on 4th, OK, then I will say 4

After whom will I visit

I will visit the left subtree

I will finish this whole

And after that I will finish the right subtree

Now when I finish it completely

That is, this dotted subtree I am making for you guys.

I will write it after finishing in full, after 4, after root, Ok

And when I visit it then some of its nodes will come

I don't know what they will be, Ok

I don't want to take that much headache for now

I'll say this is my subtree 1, Ok

I'll mark it, it's subtree 1

And I have to write this sub tree by doing it right now

I just let it be

After that I make this subtree 2, subtree 2

Luckily, we have a little subtree is just one root node

So, it's only 6, Ok

Because there is only one node

Root, Left, Right is happening

There is no Left, Right of that 6

So here it comes to 6

If it was also a big subtree

I would have written it here by making brackets

I will see this too later, Ok

Now here we have subtree 1

I should have written 1 here too

So that I know for whom I made this bracket

I made this bracket for subtree 1

So, I'll write it like this, Ok

What will I do now

Now I will solve this subtree

I will solve this subtree 1 which I have created

So, what will come first

The root node will come, Ok

I write 1 here

What will come after that

After that left

There is only one node in the left

So, I will directly write it as 5 and 2, Ok

And here it is our preorder traversal

4,

1,

5,

2,

6

So, this is our preorder traversal

for this particular tree, Ok

4, 1, 5, 2, 6

Okay

4, 1, 2, 5, 6 is the phone number of this tree

What is the phone number

Preorder

phone number means traversal

Ok, understand something like this

So, this is 4, 1, 2, 5, 6 this is our

preorder traversal of this tree

I hope everyone got it, Ok

Now how to code this

If I have been given a tree

Let's say I have made a tree man

Like we saw in our previous videos.

That we had made the tree

We had made all the pointers

In some way we had made these pointers here, this way

I'll take a black color over here

Let's also maintain a little bit of beauty

Okay

Like this

Like this

I'll take these pointers, Ok

And what is this ours, what is this node

This is a struct node, Ok

struct node

So, this is our struct node

I made (d) a bit weird, but okay

Ok, this is our struct node

What did the struct node look like to us

The struct node we saw

Inside it was a left, a right

and there was a left, right pointers

And one was our data

Data means whatever is inside our root node

Whatever is the value under our node, that's right.

So, if I write the function of preorder traversal

then how will it look like

I'm interested in this thing

So, what will I do over here

I'll write void here

and here I'll write preorder, Ok

So, this is our preorder

This will be our function

and what will I write here

I will write

struct node * root

That is, the root of the tree for which we have to preorder

Okay

What will i do in this

I will say that if the root becomes Null

That is, either you come to the leaf node

Or you are given a tree whose root is Null

We can make such a tree.

in which there is nothing inside

The whole root is Null for it, Ok

Then what will you guys do?

Then you guys will not do anything

So, if root is not Null then you will do something

So, what will you do here

You will write

if(root != Null)

What will you do if your root is not Null?

You would say that the first root

i.e., which is my data, would like to print it

So, first of all I would like to print this

So, what will I do here

I will write here, printf

And here I am writing pseudo code

I know that in the pseudo code I write here

Sometimes I don't have semicolons

I forget to close the double code.

I do this just to understand

When I come to the VS code and write this thing

Then you will understand very well, OK

So, some people also used to point out in the comment,

That you do not close semicolon, error will come

But actually, when I come to the VS code

then I take care of all these mistakes.

Ok, so what will i do here

I will write

Print the data of the root

And obviously I will write this properly, by (%d)

I will write it very well, Ok

After that in the next line I will write preorder

That is, I will call the same function recursively

for which

I will call for the left of the root

Okay

And

I'll call preorder for the right of the root

right of the root

r i g h t

Well, when I told you people about the recursion

You will remember that I told you people

Recursion solves some problems very easily

I close the bracket here.

The recursion that takes place

solves some problems very easily.

This is one of those problems

This is one of those problems which recursion solves very well.

Since the definition of preorder traversal is

that what you do first

You first print the root node

That is, first print the root you have here

And after that what you have to do

Its left sub tree, its right sub tree, it has to be printed, Ok

Root, Left, Right it is called preorder traversal, Ok

Now if I paste this function like this

then I will get 4, 1, 2, 5, 6 Ok

And this is a preorder traversal

Well, we used to have a linear data structure,

like an array,

a linked list

In that we had seen that

Whenever we use linear data structure

we can traverse it either from the beginning to the end,

or from the last to the beginning.

Why would we want to traverse

We would like to visit all the nodes

Let us say for adding all the nodes

And then let us say for searching all the nodes

That is, suppose I am looking for 7 in this tree.

No.7

So, I am not getting that right now, Ok

I went in 4, I went in 1, I went in 6, I am not getting it in 5, 2

So, I would like to traverse this in some way

4, 1, 5, 2, 6 if I am traversing like this

So, what will happen

So whatever node is there if it exists then I am finding it in it

Okay

So, hope you guys have understood what it is, OK

Now what we will do here is to code the preorder traversal

So, I had already prepared a file here.

And what did I do inside it?

That I have made up inside that file,

4, 1, 6, 5, 2

That is, the tree that I showed you a while back.

This tree looks like this

if I make this tree in front of you people

Then it looks something like this

4

And then I'll write something like this

And take 4 a step further

So, the tree finally looks like this

I made it quickly, 4, 1, 6, 5, 2 for you guys to see

That you guys at least know how tree looks, OK

So here p, p1, p2, p3, p4, I have made nodes

And after creating nodes

I have finally made the tree for your convenience.

Now we will write the function of preorder traversal, OK

The function of preorder traversal which is very simple

And

It is so easy that I will type it so fast

I will type so fast

How fast I will type

I don't even know how fast I will type

Okay

So, what will we do now

We will give it the struct *

and after that we will write the root, Ok, its root

We saw what happens in preorder traversal

The first thing you have to check in preorder traversal

if(root != Null)

What will you do if root is not equal to NULL?

You guys, here I had to write void preOrder

void preOrder

because void preorder will not return anything, Ok

Preorder is a function which will not return anything

Let me capitalize its (O) too,

struct node * root, Ok

struct node * root

That is, the node that I have created that is * root, Ok

It's so easy, it's so easy, OK

Why is it, why am I saying so much, easy, easy, easy

Because actually its easy

I will write by (%d) here

print the data of the root

and at the same time apply a similar function

That is, put the preorder

In which

in the left child of the root

and the right child of the root, Ok

here in the right

And i think this should do, that's about it

You say, it's just that easy

Yes man, it is so easy

What should I do, tell it by making it difficult

So, it's very easy, Ok

Let's see it by running

And

run it

and game over

No game over, we didn't call it, Ok

We have to call it

If we even call it here, then something will happen.

We'll call it here for (p)

We will call preorder for (p), then it will call

Now game over not must be over

4, 1, 5, 2, 6, OK

4, 1, 5, 2, 6 only came ours

preorder

4, 1, 5, 2, 6 OK

So, the preorder went very well

If you give a space, it will not look a bit good!

it would be nice

4, 1, 5, 2, 6

Okay

So, I hope you guys understand what preorder traversal is

We have come a long way in Data Structures and Algorithms.

If you haven't accessed the playlist, be sure to access it.

Because a lot of people watch my videos in between

and ask me where it is, where is it

It is very important for those people

to see the playlist from the beginning

That's all in this video for now

Thankyou so much guys for watching this video

And i will see you

Next time.