Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/0a157cdf8eab4b88d40eb8079c877f99 to your computer and use it in GitHub Desktop.
Save jianminchen/0a157cdf8eab4b88d40eb8079c877f99 to your computer and use it in GitHub Desktop.
Preorder Tree Traversal - using stack - iterative solution
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace preorderTraversal
{
public class TreeNode
{
public int value { get; set; }
public TreeNode left { get; set; }
public TreeNode right { get; set; }
public override string ToString()
{
return value.ToString();
}
public TreeNode(int v)
{
value = v;
}
}
class Program
{
static void Main(string[] args)
{
TreeNode node1 = new TreeNode(1);
node1.left = new TreeNode(2);
node1.left.left = new TreeNode(3);
node1.left.right = new TreeNode(4);
node1.right = new TreeNode(5);
node1.right.left = new TreeNode(6);
node1.right.right = new TreeNode(7);
List<TreeNode> preorderNodes = preOrderTraversal(node1);
TreeNode[] arr = preorderNodes.ToArray();
}
/*
* 1. Manually review each line, each variable in the function, make it best;
* 2. Go over a test case, and do some static analysis, execute the code manually.
* go over the tree with value 1 - 9, and then, make sure that
* the output will work exactly the correct order.
*
* 1
* / \
* 2 5
* / \ / \
* 3 4 6 7
*
* preorder: 1 2 3 4 5 6 7
*
*/
public static List<TreeNode> preOrderTraversal(TreeNode root)
{
if (root == null)
return null;
List<TreeNode> preOrderNodes = new List<TreeNode>();
TreeNode runner = root;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(runner);
while (true)
{
if (stack.Count == 0)
break;
runner = (TreeNode)stack.Pop();
preOrderNodes.Add(runner);
if(runner.right != null)
stack.Push(runner.right);
if (runner.left != null)
stack.Push(runner.left);
}
return preOrderNodes;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment