Binary Tree Preorder Traversal Problem

Problem Description

Given a binary tree, return the preorder traversal of its nodes’ values.

Example
Given binary tree {1,#,2,3}:


return [1,2,3].

Challenge
Can you do it without recursion?

Solution 1:
Non recursion

Solution 2 (recursion – divide & conquer)

Divide:
ArrayList lstLeft = preorderTraversal(root.left)
ArrayList lstRight = preorderTraversal(root.right)

Conquer:
lst.add(root.val);
lst.add(lstLeft);
lst.add(lstRight);

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on RedditShare on StumbleUponEmail this to someoneShare on TumblrDigg this

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">