- Problem Statement<\/a><\/li>
- 1. Recursive Approach<\/a><\/li>
- Implementation of Recursive Approach<\/a><\/li>
- C++ Implementation<\/a><\/li>
- Java Implementation<\/a><\/li>
- Python Implementation<\/a><\/li><\/ul><\/ul>
- 2. Iterative Approach<\/a><\/li>
- Implementation of Iterative Approach<\/a><\/li>
- C++ Implementation of Iterative Approach<\/a><\/li>
- Java Implementation of Iterative Approach<\/a><\/li>
- Python Implementation of Iterative Approach<\/a><\/li><\/ul><\/ul>
- Practice Questions<\/a><\/li>
- Frequently Asked Questions<\/a><\/li>
- Q.1: Is there any way to print the preorder traversal in O(1) space (Including function call stack)?<\/a><\/li>
- Q.2: Can we write preorder traversal from Inorder and Postorder traversal?<\/a><\/li>
- Q.3: Is Preorder sufficient to maintain the structure of the tree?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
Given a binary tree, the task is to print the preorder traversal of the tree.<\/p>\n\n\n\n
Pre-Order is a way to traverse the binary tree in which our directions are fixed <\/p>\n\n\n\n
i.e. root-> left – > right<\/strong>. It means first we will traverse the root of the tree and then go to its left subtree and after traversing that subtree we will move to its right part of the subtree.<\/p>\n\n\n\n
<\/figure>\n\n\n\n
Example:<\/p>\n\n\n\n
- Input:<\/strong> [A,B,C,D,E,F,G,NULL,NULL,NULL,NULL]<\/li>
- Output:<\/strong> [A,B,DE,C,F,G]<\/li><\/ul>\n\n\n\n
Explanation:<\/strong><\/p>\n\n\n\n
- Input:<\/strong> [1,2,3,4,5,6,7,-1,-1,-1,-1]<\/li>
- Output:<\/strong> [1,2,4,5,3,6,7]<\/li><\/ul>\n\n\n\n
1. Recursive Approach<\/h2>\n\n\n\n
For implementing a recursive approach we first call the root of the current tree and then traverse the left and right subtree.<\/p>\n\n\n\n
Implementation of Recursive Approach<\/h3>\n\n\n\n
C++ Implementation<\/h4>\n\n\n\n
void printPreorder(struct Node* node)\n{\n if (node == NULL)\n return;\n \n \/* first print data of node *\/\n cout << node->data << \" \";\n \n \/* then recur on left subtree *\/\n printPreorder(node->left);\n \n \/* now recur on right subtree *\/\n printPreorder(node->right);\n}<\/pre>\n\n\n\nJava Implementation<\/h4>\n\n\n\n
public List < Integer > preorderTraversal(TreeNode root) {\n List < Integer > pre = new LinkedList < Integer > ();\n if (root == null) return pre;\n pre.add(root.val);\n pre.addAll(preorderTraversal(root.left));\n pre.addAll(preorderTraversal(root.right));\n return pre;\n}<\/pre>\n\n\n\nPython Implementation<\/h4>\n\n\n\n
def printPreorder(root):\n \n if root:\n \n # First print the data of node\n print(root.val),\n \n # Then recur on left child\n printPreorder(root.left)\n \n # Finally recur on right child\n printPreorder(root.right)<\/pre>\n\n\n\n
- Time complexity:<\/strong> O(N), Where N is the size of the binary tree.<\/li>
- Space complexity:<\/strong> O(1) If we don\u2019t consider the function call stack, else O(h), h is the height of the tree.<\/li><\/ul>\n\n\n\n
2. Iterative Approach<\/h2>\n\n\n\n
The iterative approach uses stack data structure to print the preorder traversal. Follow the below steps.<\/p>\n\n\n\n
- Create an empty stack, Push the root node to the stack.<\/li>
- Do the following while the stack is not empty.<\/li>
- Pop an item from the stack and print it.<\/li>
- Push the right child of the popped item to stack.<\/li>
- Push the left child of the popped item to stack.<\/li><\/ul>\n\n\n\n
Implementation of Iterative Approach<\/h3>\n\n\n\n
C++ Implementation of Iterative Approach<\/h4>\n\n\n\n
vector < int > preorderTraversal(TreeNode * root) {\n stack < TreeNode * > nodeStack;\n vector < int > result;\n \/\/base case\n if (root == NULL)\n return result;\n nodeStack.push(root);\n while (!nodeStack.empty()) {\n TreeNode * node = nodeStack.top();\n result.push_back(node -> val);\n nodeStack.pop();\n if (node -> right)\n nodeStack.push(node -> right);\n if (node -> left)\n nodeStack.push(node -> left);\n }\n return result;\n\n}<\/pre>\n\n\n\nJava Implementation of Iterative Approach<\/h4>\n\n\n\n
public List < Integer > preorderTraversal(TreeNode node) {\n List < Integer > list = new LinkedList < Integer > ();\n Stack < TreeNode > rights = new Stack < TreeNode > ();\n while (node != null) {\n list.add(node.val);\n if (node.right != null) {\n rights.push(node.right);\n }\n node = node.left;\n if (node == null && !rights.isEmpty()) {\n node = rights.pop();\n }\n }\n return list;\n}<\/pre>\n\n\n\nPython Implementation of Iterative Approach<\/h4>\n\n\n\n
<\/p>\n\n\n\n
def preorderTraversal(self, root):\n ret = []\n stack = [root]\n while stack:\n node = stack.pop()\n if node:\n ret.append(node.val)\n stack.append(node.right)\n stack.append(node.left)\n return ret<\/pre>\n\n\n\n
- Time complexity:<\/strong> O(N), Where N is the size of the binary tree.<\/li>
- Space complexity:<\/strong> O(N)<\/li><\/ul>\n\n\n\n
\n\n\n\nPractice Questions<\/h2>\n\n\n\n
Preorder Traversal<\/a>
Valid BST from Preorder<\/a><\/p>\n\n\n\n
\n\n\n\nFrequently Asked Questions<\/h2>\n\n\n\n
Q.1: Is there any way to print the preorder traversal in O(1) space (Including function call stack)?<\/span><\/h3>\n\n\n\n
Ans: Yes, using Morris traversal.<\/p>\n\n\n\n
Q.2: Can we write preorder traversal from Inorder and Postorder traversal?<\/span><\/h3>\n\n\n\n
Ans: Yes.<\/p>\n\n\n\n
Q.3: Is Preorder sufficient to maintain the structure of the tree?<\/span><\/h3>\n\n\n\n
Ans: No, we need a Preorder and Inorder to find a unique structure.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a binary tree, the task is to print the preorder traversal of the tree. Pre-Order…\n","protected":false},"author":5,"featured_media":2268,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[393],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2266"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2266"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2266\/revisions"}],"predecessor-version":[{"id":20046,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2266\/revisions\/20046"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2268"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2266"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2266"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2266"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- Space complexity:<\/strong> O(N)<\/li><\/ul>\n\n\n\n
- Time complexity:<\/strong> O(N), Where N is the size of the binary tree.<\/li>
- Space complexity:<\/strong> O(1) If we don\u2019t consider the function call stack, else O(h), h is the height of the tree.<\/li><\/ul>\n\n\n\n
- Output:<\/strong> [1,2,4,5,3,6,7]<\/li><\/ul>\n\n\n\n
- Output:<\/strong> [A,B,DE,C,F,G]<\/li><\/ul>\n\n\n\n
- Q.2: Can we write preorder traversal from Inorder and Postorder traversal?<\/a><\/li>
- Java Implementation of Iterative Approach<\/a><\/li>
- C++ Implementation of Iterative Approach<\/a><\/li>
- Java Implementation<\/a><\/li>
- C++ Implementation<\/a><\/li>
- 1. Recursive Approach<\/a><\/li>
![\"Example\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-1.jpg\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-1.jpg\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-1.jpg\")
<\/figure>\n\n\n\n