Given the root of a binary tree, return the preorder traversal of its nodes' values. Example 1:Input: root = [1,null,2,3]Output: [1,2,3]Example 2:Input: root = []Output: []Example 3:Input: root = [1]Output: [1] Constraints:The number of nodes in the tree is in the range [0, 100].-100 <= Node.val <= 100 Follow up: Recursive solution is trivial, could you do it iteratively?
Question
Given the root of a binary tree, return the preorder traversal of its nodes' values. Example 1:Input: root = [1,null,2,3]Output: [1,2,3]Example 2:Input: root = []Output: []Example 3:Input: root = [1]Output: [1] Constraints:The number of nodes in the tree is in the range [0, 100].-100 <= Node.val <= 100 Follow up: Recursive solution is trivial, could you do it iteratively?
Solution
Sure, I can help with that. Here's a Python solution using an iterative approach with a stack:
def preorderTraversal(root):
if root is None:
return []
stack, output = [root, ], []
while stack:
root = stack.pop()
if root is not None:
output.append(root.val)
if root.right is not None:
stack.append(root.right)
if root.left is not None:
stack.append(root.left)
return output
Here's how it works:
- Initialize an empty list
outputand a stack with the root node in it. - While there are still nodes in the stack:
- Pop a node from the stack and add its value to
output. - If the popped node has a right child, add it to the stack.
- If the popped node has a left child, add it to the stack.
- Pop a node from the stack and add its value to
- Return the
outputlist.
This algorithm works because in a preorder traversal, you visit the
Similar Questions
In preorder traversal of a binary tree the second step is ____________Select one:a. traverse the right subtreeb. traverse the left subtreec. traverse right subtree and visit the rootd. visit the root
Given a Linked List Representation of Complete Binary Tree. Your task is to construct the Binary tree from the given linkedlist and return the root of the tree.The result will be judged by printing the level order traversal of the Binary tree. Note: The complete binary tree is represented as a linked list in a way where if the root node is stored at position i, its left, and right children are stored at position 2*i+1, and 2*i+2 respectively. H is the height of the tree and this space is used implicitly for the recursion stack.
Complete below code of Preorder traversalPreorder(node* root){If(a-----------------){cout<<root->data;b--------------------------;preorder(root->right);}} a.NULL b.root->lefta.root==NULL b.Preorder(root->left);a.root!=NULL b.Preorder(root->left);a.root!=NULL b.root->left
Which of the following traversal methods can be used to obtain a sorted sequence of elements in a binary search tree?PreorderPostorderLevel orderInorder
The inorder and preorder traversal of a binary tree are Inorder: d b e a p q r PreOrder: a b d e q p r The postorder traversal of the binary tree is: (A) d e b p r q a (B) e d b r p q a (C) e d b p r q a (D) d e p r b q a
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.