Tree: Preorder Traversal

  • + 0 comments

    In C# the input description is horrible. There is no code given, you need to parse input from stdin. First line is number of nodes, second line is list of nodes from which you first need to create the tree, then traverse it. In e.g. Python, the entire tree is already created with appropriate tree structure class. Here is a C# solution:

    using System; using System.Collections.Generic; using System.IO; class Solution { public static List res = new List();

    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        var lines = new List<string>();
        var line ="";
        while((line = Console.ReadLine()) != null && line !=""){
            lines.Add(line);
        }
        if(lines.Count() == 0) return;
    
        //Console.WriteLine(string.Join(",", lines));
        TreeNode root = null;
        foreach(string val in lines[1].Split(" ")){
            var asInt = int.Parse(val);
            root = Insert(root, asInt);
        }
        PreOrderTraverse(root);
        if(res.Count < 2) return;
        Console.WriteLine(string.Join(" ", res));
    }
    
    public static void PreOrderTraverse(TreeNode root){
        if(root == null) return;
        res.Add(root.Value.ToString());
        PreOrderTraverse(root.Left);
        PreOrderTraverse(root.Right);
    }
    
    public static TreeNode Insert(TreeNode? root, int val){
        if(root == null){
            return new TreeNode(val);
        }
        if(val < root.Value){
            root.Left = Insert(root.Left, val);
            return root;
        }else{
            root.Right = Insert(root.Right, val);
        }
        return root;
    }
    

    }

    public class TreeNode(int value, TreeNode? left = null, TreeNode? right = null){ public int Value {get; set;} = value; public TreeNode? Left {get; set;} = left; public TreeNode? Right {get; set;} = right; }