Binary Tree Preorder Traversal Editorial

Practice Problem Link: Binary Tree Preorder Traversal

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a binary tree, return the preorder traversal of its elements.

Approach

To get the preorder traversal of a binary tree first visit the current root, then the left subtree followed by the right subtree for each node recursively.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
void getPreorderTraversalUtil(Node* root, vector<int> &traversal) {
	if (root == NULL) {
		return;
	}
	traversal.push_back(root->data);
	getPreorderTraversalUtil(root->left, traversal);
	getPreorderTraversalUtil(root->right, traversal);
}

vector<int> getPreorderTraversal(Node* root) {
	vector<int> traversal;
	getPreorderTraversalUtil(root, traversal);
	return traversal;
}

Java

/* This is the Node class definition

class Node {
	public Node left;
    public Node right;
    int data;

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	void getPreorderTraversalUtil(Node root, List<Integer> traversal) {
		if (root == null) {
			return;
		}
		traversal.add(root.data);
		getPreorderTraversalUtil(root.left, traversal);
		getPreorderTraversalUtil(root.right, traversal);
	}
	List<Integer> getPreorderTraversal(Node root) {
		List<Integer> traversal = new ArrayList<Integer>();
		getPreorderTraversalUtil(root, traversal);
		return traversal;
	}
}