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.
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
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
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
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?
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.
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()
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.
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
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.
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
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?
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; }
