1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
#include <bits/stdc++.h>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
vector<vector<int>> treeTraversal(TreeNode* root) {
// Vectors to store the traversals
vector<int> pre, in, post;
// If the tree is empty, return empty traversals
if (root == nullptr) return { pre, in, post };
// Stack to maintain nodes and their traversal state
stack<pair<TreeNode*, int>> st;
// Start with the root node and state 1 (preorder)
st.push({ root, 1 });
while (!st.empty()) {
// Get the top element from the stack
auto [node, state] = st.top();
st.pop();
// Process the node based on its state
if (state == 1) {
// Preorder: Add node data
pre.push_back(node->data);
// Change state to 2 (inorder) for this node
st.push({ node, 2 });
// Push left child onto the stack for processing
if (node->left != nullptr) {
st.push({ node->left, 1 });
}
} else if (state == 2) {
// Inorder: Add node data
in.push_back(node->data);
// Change state to 3 (postorder) for this node
st.push({ node, 3 });
// Push right child onto the stack for processing
if (node->right != nullptr) {
st.push({ node->right, 1 });
}
} else {
// Postorder: Add node data
post.push_back(node->data);
}
}
// Return the traversals as a 2D vector
return { in, pre, post};
}
};
// Main function to test the tree traversal
int main() {
// Creating a sample binary tree
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
Solution sol;
vector<vector<int>> traversals = sol.treeTraversal(root);
// Print Preorder traversal
cout << "Preorder traversal: ";
for (int val : traversals[0]) cout << val << " ";
cout << endl;
// Print Inorder traversal
cout << "Inorder traversal: ";
for (int val : traversals[1]) cout << val << " ";
cout << endl;
// Print Postorder traversal
cout << "Postorder traversal: ";
for (int val : traversals[2]) cout << val << " ";
cout << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110
import java.util.*;
/**
* Definition for a binary tree node.
*/
class TreeNode {
int data;
TreeNode left, right;
TreeNode(int val) {
this.data = val;
this.left = null;
this.right = null;
}
}
// Helper class to store a TreeNode and its traversal state
class NodeState {
TreeNode node;
int state;
NodeState(TreeNode node, int state) {
this.node = node;
this.state = state;
}
}
class Solution {
public List<List<Integer>> treeTraversal(TreeNode root) {
// Lists to store the traversals
List<Integer> pre = new ArrayList<>();
List<Integer> in = new ArrayList<>();
List<Integer> post = new ArrayList<>();
// If the tree is empty, return empty traversals
if (root == null) return Arrays.asList(pre, in, post);
// Stack to maintain nodes and their traversal state
Stack<NodeState> st = new Stack<>();
// Start with the root node and state 1 (preorder)
st.push(new NodeState(root, 1));
while (!st.isEmpty()) {
// Get the top element from the stack
NodeState top = st.pop();
TreeNode node = top.node;
int state = top.state;
// Process the node based on its state
if (state == 1) {
// Preorder: Add node data
pre.add(node.data);
// Change state to 2 (inorder) for this node
st.push(new NodeState(node, 2));
// Push left child onto the stack for processing
if (node.left != null) {
st.push(new NodeState(node.left, 1));
}
} else if (state == 2) {
// Inorder: Add node data
in.add(node.data);
// Change state to 3 (postorder) for this node
st.push(new NodeState(node, 3));
// Push right child onto the stack for processing
if (node.right != null) {
st.push(new NodeState(node.right, 1));
}
} else {
// Postorder: Add node data
post.add(node.data);
}
}
// Return the traversals as a list of lists
return Arrays.asList(in, pre, post);
}
}
class Main {
public static void main(String[] args) {
// Creating a sample binary tree
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
Solution sol = new Solution();
List<List<Integer>> traversals = sol.treeTraversal(root);
// Print Preorder traversal
System.out.print("Preorder traversal: ");
for (int val : traversals.get(0)) System.out.print(val + " ");
System.out.println();
// Print Inorder traversal
System.out.print("Inorder traversal: ");
for (int val : traversals.get(1)) System.out.print(val + " ");
System.out.println();
// Print Postorder traversal
System.out.print("Postorder traversal: ");
for (int val : traversals.get(2)) System.out.print(val + " ");
System.out.println();
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
from typing import List
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val: int):
self.data = val
self.left = None
self.right = None
class Solution:
def tree_traversal(self, root: TreeNode):
# Lists to store the traversals
pre, in_order, post = [], [], []
# If the tree is empty, return empty traversals
if root is None:
return [pre, in_order, post]
# Stack to maintain nodes and their traversal state
stack = [(root, 1)]
while stack:
# Get the top element from the stack
node, state = stack.pop()
# Process the node based on its state
if state == 1:
# Preorder: Add node data
pre.append(node.data)
# Change state to 2 (inorder) for this node
stack.append((node, 2))
# Push left child onto the stack for processing
if node.left:
stack.append((node.left, 1))
elif state == 2:
# Inorder: Add node data
in_order.append(node.data)
# Change state to 3 (postorder) for this node
stack.append((node, 3))
# Push right child onto the stack for processing
if node.right:
stack.append((node.right, 1))
else:
# Postorder: Add node data
post.append(node.data)
# Return the traversals as a list of lists
return [in_order, pre, post]
# Main function to test the tree traversal
if __name__ == "__main__":
# Creating a sample binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
sol = Solution()
traversals = sol.tree_traversal(root)
# Print Preorder traversal
print("Preorder traversal:", *traversals[0])
# Print Inorder traversal
print("Inorder traversal:", *traversals[1])
# Print Postorder traversal
print("Postorder traversal:", *traversals[2])
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
/**
* Definition for a binary tree node.
*/
class TreeNode {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
}
class Solution {
treeTraversal(root) {
// Arrays to store the traversals
let pre = [], inOrder = [], post = [];
// If the tree is empty, return empty traversals
if (root === null) return [pre, inOrder, post];
// Stack to maintain nodes and their traversal state
let stack = [[root, 1]];
while (stack.length > 0) {
// Get the top element from the stack
let [node, state] = stack.pop();
// Process the node based on its state
if (state === 1) {
// Preorder: Add node data
pre.push(node.data);
// Change state to 2 (inorder) for this node
stack.push([node, 2]);
// Push left child onto the stack for processing
if (node.left !== null) {
stack.push([node.left, 1]);
}
} else if (state === 2) {
// Inorder: Add node data
inOrder.push(node.data);
// Change state to 3 (postorder) for this node
stack.push([node, 3]);
// Push right child onto the stack for processing
if (node.right !== null) {
stack.push([node.right, 1]);
}
} else {
// Postorder: Add node data
post.push(node.data);
}
}
// Return the traversals as an array of arrays
return [inOrder, pre, post];
}
}
// Main function to test the tree traversal
(function() {
// Creating a sample binary tree
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
let sol = new Solution();
let traversals = sol.treeTraversal(root);
// Print Preorder traversal
console.log("Preorder traversal:", traversals[0].join(" "));
// Print Inorder traversal
console.log("Inorder traversal:", traversals[1].join(" "));
// Print Postorder traversal
console.log("Postorder traversal:", traversals[2].join(" "));
})();
