Tree: Preorder Traversal

Sort by

recency

|

9 Discussions

|

  • + 0 comments

    Java O(n)

     public static void preOrder(Node root) {
            if (root != null) {
                System.out.print(root.data + " ");
                preOrder(root.left);
                preOrder(root.right);
            }
        }
    
  • + 0 comments

    C++, iterative with a stack instead of recursive. We visit each node, then push its right and then left (in reverse order) so they are visited in the correct order as we later pop the stack.

    The Hackerrank solution code doesn't include <vector> which you kinda need, so I hacked a way to get it included. Here's the full text of my solution, verbatim (it intentionally ends with an open brace).

        void preOrder(Node *root);
    };
    #include <vector>
    #include <utility>
    
    void Solution::preOrder(Node* root) {
        std::vector<Node*> stack;
        
        stack.reserve(20);
        
        stack.push_back(root);
        while (!stack.empty()) {
            auto node = stack.back();
            stack.pop_back();
            std::cout << node->data << ' ';
            if (node->right)
                stack.push_back(node->right);
            if (node->left)
                stack.push_back(node->left);
        }
    }
    
    struct HACK {
    
  • + 0 comments

    function preOrder(root) {

     if(root){
        process.stdout.write(`${root.data} `);
        preOrder(root.left)
        preOrder(root.right) 
    }
    
  • + 0 comments

    Python

    def preOrder(root):
        if root:
            print(root.info, end = ' ')
            preOrder(root.left)
            preOrder(root.right)
    
  • + 0 comments

    Recursive Method- TC is O(n log n) and SC is O(1)

    def preOrder(root):

    if root is not None:
        print(root.info,end=" ")
        preOrder(root.left)
        preOrder(root.right)
    

    Iterative Method- TC is O(n) and SC is O(1)

    def preOrder(root):

    stack= [root]
    result = []
    
    if root is None:return []
    
    while stack:
        root = stack.pop()
        result.append(root.info)
        if root.right:
            stack.append(root.right)
        if root.left :
            stack.append(root.left)
    print (*result)