Preorder Traversal in a Binary Tree (With C Code)
Summary
TLDRIn 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
🌳 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.
💻 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.
🚀 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.
Mindmap
Keywords
💡Preorder Traversal
💡Root Node
💡Subtree
💡Tree Traversal
💡Recursive Function
💡Data Structure
💡Struct Node
💡Null Check
💡Pseudo Code
💡Binary Tree
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.
Voir Plus de Vidéos Connexes
Depth First Search (DFS) Graph Traversal in Data Structures
Traversing a Single Linked List (Counting the Nodes)
Subtree of Another Tree - Leetcode 572 - Python
Binary Search Trees (BST) Explained in Animated Demo
LeetCode Problem: 226. Invert Binary Tree | Java Solution
Solving My Google Phone Interview Question
5.0 / 5 (0 votes)