Print all ROOT to LEAF paths in a binary tree
ฝัง
- เผยแพร่เมื่อ 20 ก.ย. 2024
- 1 .Given a binary tree. Print all the root to leaf paths in the tree.
2. print out all of its root-to-leaf paths one per line.
Traversals of a binary tree (inorder traversal) :- • Print all ROOT to LEAF...
![[FULL EP.16] เซียนพาลุย "เผือก-ฟรอยด์" กรี๊ดลั่น จนปูหนี | เฮ็ดอย่างเซียนหรั่ง | One Playground](http://i.ytimg.com/vi/FsqUvwS3b-Y/mqdefault.jpg)
I love this guy the most when it comes to videos. he doesn't just write the code, he draws out all the steps the code actually takes, which makes it much more intuitive.
Thanks
Queue is better choice as we are printing FIFO order and stack is LIFO. Great tutorial and good explanation.
haa...how can we print stack in opp direction, way too effort
But at the time of removing an element, in FIFO root element will be removed first instead of a leaf node. So the queue is also a not good DS to solve this problem. Instead of it, we can use Double-ended queues.
Is it only me who thinks it's actually a mixture of in-order and pre-order traversal? Have a look at 7:10.
1> pushing data to stack
2> recursive call with left child
3> printing stack
4> recursive call with right child
I was thinking the same, I believe its actually a pre-order traversal.
Thank you apnay aik kameenay teacher say jaan bacha li
Thank you, Great, only I would say, it has to be Queue instead of stack, the stack will print in reversed order. thank you, its really great tutorial.
but if we will use stack then ,when we away from leaf node ,removal of top node is difficult.Instead we should use a deque.
Then how will you pop it.Deque may be a choice but Instead You can implement your own stack using array and print elements starting with index 0 till top of stack.
It can be easily done if you using list(array) as the stack.
See solution- leetcode.com/problems/binary-tree-paths/discuss/531333/Python3-Runtime%3A-20ms-InOrder-Traversal-%2B-Stack
Thanks for making trees simple
For those who are doubting how to print stack in reverse order. Instead of using stack you can use vector as it has all those functionality of push_back() and pop_back()
Thank you for your lesson, Sir! It helped me a lot!
Your approach is efficient if we have to print leat to root path but here we have to print root to leaf path so either we can use list or deque to solve this problem, every time reversing the stack ( not by taking reference ) or store it an a container is not an efficient technique.
sir if we print the stack then we have to one by one pop all elements uot of stack which will not work
Thank you for wonderful tutorial!
for the first print, "a,b,d".... how do you print the first path without popping everything from the list. in the next step you only pop d on the top but not everything else
great video! thank you for your help!
Hello Vivek,
Nice efforts from you.
I have few queries. Please help me understand.
1. According to code when we reach the leaf node, program will print the path from root to leaf. For that elements should be popped from the stack. For ex: to print "abd", one needs to do pop() 3 times. Now, the stack is empty. Why we need to pop() again ? Does print_stack() is followed in different way.
2. If we use stack to print the path then "abd" will be "dba" when we print
Please correct if wrong.
Thanks
Great idea. Well done.
i believe we can use a DFS based approach on this?no need of extra space? Also, can someon show me a reference to an iterative solution to this? can we think an iterative version will use a stack, and it will be the same exact way we would perform a DFS(with Stack) on a graph, except we won't need a "visited" check?
Thank you for the clear explanation. However I think printing the stack would print the elements in LIFO order. Which means that you would need to pop from stack and hold the values some where else or some how print in reverse order. Correct?
Correct
Using queue is more efficient rather than a stack to display a root
Hello sir,
longestLeftPath(Node* n,Node** start)
function should find longest path in binary tree only count if we move left in BST ,also function should return reference of node where longest left path i BST start . Any idea ? Thanks for videos.
It is also can be done using pre-order:
void preorder(Node* root, stack s){
if( root == null ) return;
s.push(&root);
preorder(root->left,s);
preorder(root->right,s);
if( root -> left == null && root -> right == null)
printStack(s);
s.pop();
return;
}
It is not pre order , it is post order
You're correct
Sir ... i think in above video , we are using preorder traversal instead of inorder . please clarify me if i am wrong
any thing is fine. A + B is in order, +AB is pre order, AB+ is post order. If I say only AB. which order it is. He is just using AB.
Hi vivekanand.. Thanks for the nice explanation, but how do you print the stack from bottom ?
I written whole code as follows:
int intArray[10240];
int counter = 0;
void printAllPaths(Node* root) {
if(root == NULL)
return;
intArray[counter] = root->val;
counter++;
printAllPaths(root->left);
if(root->left == NULL && root->right == NULL) {
for(int i=0; i
nice explanation
Thank youuuuu very muchhh sirrrr
Thank you soo much
Hi, I have a doubt in the way, push(root->data ) should come before we checking if (root ==null) and print should come in if (root ==null ) condition. Correct me if am worng
So what if root is null. It will break the code if you do that before checking (root == null)
we can also do it using pos-torder traversal
sir ,could u explain,..Given a binary tree, find the maximum path sum?
yes sure atharsh ....very soon i will uploadvideo in this week.
#include
#include
using namespace std;
struct node{
int data;
struct node *left,*right;
};
struct node *newnode(struct node *start,int data)
{
struct node *temp=(struct node *)malloc(sizeof(struct node));
temp->data=data;
temp->left=temp->right=NULL;
return temp;
}
void postorder(struct node *start)
{
if(start==NULL)
return;
postorder(start->left);
postorder(start->right);
coutright)
q.push(temp->right);
}
}
coutright=newnode(root,7);
postorder(root);
find_level_maximum_sum(root);
return 0;
}
I think istead of stack, it's better to use queue, so that order would be root to child
But while popping out element you need to remove it from the end of the queue. So either case would work fine!
Please add code link to your description
you are too good
Sir Please upload video on Trie Data structure with Problems also.
sir could you do a program for find the sum of the diagonal elements in a binary tree
Yes sure very soon Veerraju..!
while printing stack (print_stack()) we have to pop() out all the elements then how will we get track of last values
Yes you are right......but in this case while printing you just go through the stack_array and print that array , don't pop() values . You can always display the current elements in the stack. Just take the snapshot of the stack at that instant. You just have to keep a counter of how many elements are present in the array. Here I have just focussed on the algorithm for root to leaf paths....but if you say I will mail you the code for the same. Hey thanks for helping me to get better.
after ending the print stack scope we have to go to the next line to execute pop
if(root.left==null && root.right==null){
print stack;
} pop stack;
bhai jawab milla to muje bhi btao kese stack ko intact rakha without popping?
Sir please mention time and space complexities in every video. You miss it everytime.
Wonderfullllllllllllllll
apne return type galat liya h shayad it show be a node* type;
I need a non-recursive algorithm, can you tell me?
Same logic using Deque(Java implementation)
public static void rootToLeafPaths(TreeNode root,List al,Deque q){
if(root==null) {
return;
}
q.add(root);
rootToLeafPaths(root.left, al, q);
if(!q.isEmpty() && root.left==null && root.right==null) {
List ls=new ArrayList();
Iterator it=q.iterator();
while(it.hasNext()) {
TreeNode temp=(TreeNode) it.next();
ls.add(temp.val);
}
al.add(new ArrayList(ls));
}
rootToLeafPaths(root.right, al, q);
q.removeLast();
}
Your name is apt for u
he is good with theory but code is wrong
just use list instead of stack
listt;
void print_path()
{
for(list::iterator it=t.begin();it!=t.end();it++)
{
Node *temp=*it;
cout
pythonistas no worries: use reversed ()
hehe....that's true...!!! pythonistas are legends..