Traverse the binary tree in left → root → right order using recursion. For each node, recurse into the left subtree first, then record the current node's value, and finally recurse into the right subtree.
Use an explicit stack to simulate the recursive call stack. Push nodes onto the stack while traversing left. When there are no more left children, pop from the stack, record the value, and move to the right child.
""" 0094.1 - Binary Tree Inorder Traversal - Solution 1 - Recursive DFS """
#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
"""Inorder Traversal Function"""
ans: List[int] = []
def dfs(node: Optional[TreeNode]):
if node is None:
return
dfs(node.left)
ans.append(node.val)
dfs(node.right)
dfs(root)
return ans
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
root1 = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(Solution().inorderTraversal(root1)) # [1, 3, 2]
print(Solution().inorderTraversal(None)) # []
print(Solution().inorderTraversal(TreeNode(1))) # [1]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()/** 0094.1 - Binary Tree Inorder Traversal - Solution 1 - Recursive DFS */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
/** Inorder Traversal Function */
inorderTraversal(root) {
const ans = [];
const dfs = (node) => {
if (!node) return;
dfs(node.left);
ans.push(node.val);
dfs(node.right);
};
dfs(root);
return ans;
}
}
/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
const root1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
console.log(new Solution().inorderTraversal(root1)); // [1, 3, 2]
console.log(new Solution().inorderTraversal(null)); // []
console.log(new Solution().inorderTraversal(new TreeNode(1))); // [1]
}
/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();/** 0094.1 - Binary Tree Inorder Traversal - Solution 1 - Recursive DFS */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class TreeNode {
constructor(
public val: number = 0,
public left: TreeNode | null = null,
public right: TreeNode | null = null,
) {}
}
class Solution {
/** Inorder Traversal Function */
inorderTraversal(root: TreeNode | null): number[] {
const ans: number[] = [];
const dfs = (node: TreeNode | null) => {
if (!node) return;
dfs(node.left);
ans.push(node.val);
dfs(node.right);
};
dfs(root);
return ans;
}
}
/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
const root1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
console.log(new Solution().inorderTraversal(root1)); // [1, 3, 2]
console.log(new Solution().inorderTraversal(null)); // []
console.log(new Solution().inorderTraversal(new TreeNode(1))); // [1]
}
/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();// 0094.1 - Binary Tree Inorder Traversal - Solution 1 - Recursive DFS
package main
/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"
/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func inorderTraversal(root *TreeNode) []int {
ans := []int{}
var dfs func(*TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
dfs(node.Left)
ans = append(ans, node.Val)
dfs(node.Right)
}
dfs(root)
return ans
}
func testcase() {
root1 := &TreeNode{Val: 1, Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}}}
fmt.Println(inorderTraversal(root1)) // [1 3 2]
fmt.Println(inorderTraversal(nil)) // []
fmt.Println(inorderTraversal(&TreeNode{Val: 1})) // [1]
}
/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
testcase()
}// 0094.1 - Binary Tree Inorder Traversal - Solution 1 - Recursive DFS
use std::rc::Rc;
use std::cell::RefCell;
#[derive(Debug)]
struct TreeNode {
val: i32,
left: Option<Rc<RefCell<TreeNode>>>,
right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
fn new(val: i32) -> Rc<RefCell<TreeNode>> {
Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
}
}
struct Solution;
impl Solution {
pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
fn dfs(node: Option<Rc<RefCell<TreeNode>>>, ans: &mut Vec<i32>) {
if let Some(n) = node {
let nb = n.borrow();
dfs(nb.left.clone(), ans);
ans.push(nb.val);
dfs(nb.right.clone(), ans);
}
}
let mut ans: Vec<i32> = Vec::new();
dfs(root, &mut ans);
ans
}
}
fn main() {
let root1 = TreeNode::new(1);
let node2 = TreeNode::new(2);
let node3 = TreeNode::new(3);
node2.borrow_mut().left = Some(node3.clone());
root1.borrow_mut().right = Some(node2.clone());
println!("{:?}", Solution::inorder_traversal(Some(root1))); // [1, 3, 2]
}""" 0094.2 - Binary Tree Inorder Traversal - Solution 2 - Iterative with Stack """
#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
"""Inorder Traversal Function"""
ans: List[int] = []
stack: list[TreeNode] = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
ans.append(current.val)
current = current.right
return ans
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
root1 = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(Solution().inorderTraversal(root1)) # [1, 3, 2]
print(Solution().inorderTraversal(None)) # []
print(Solution().inorderTraversal(TreeNode(1))) # [1]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()/** 0094.2 - Binary Tree Inorder Traversal - Solution 2 - Iterative with Stack */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
/** Inorder Traversal Function */
inorderTraversal(root) {
const ans = [];
const stack = [];
let current = root;
while (current || stack.length) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop();
ans.push(current.val);
current = current.right;
}
return ans;
}
}
/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
const root1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
console.log(new Solution().inorderTraversal(root1)); // [1, 3, 2]
console.log(new Solution().inorderTraversal(null)); // []
console.log(new Solution().inorderTraversal(new TreeNode(1))); // [1]
}
/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();/** 0094.2 - Binary Tree Inorder Traversal - Solution 2 - Iterative with Stack */
/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class TreeNode {
constructor(
public val: number = 0,
public left: TreeNode | null = null,
public right: TreeNode | null = null,
) {}
}
class Solution {
/** Inorder Traversal Function */
inorderTraversal(root: TreeNode | null): number[] {
const ans: number[] = [];
const stack: TreeNode[] = [];
let current: TreeNode | null = root;
while (current || stack.length) {
while (current) {
stack.push(current);
current = current.left;
}
current = stack.pop()!;
ans.push(current.val);
current = current.right;
}
return ans;
}
}
/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
const root1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
console.log(new Solution().inorderTraversal(root1)); // [1, 3, 2]
console.log(new Solution().inorderTraversal(null)); // []
console.log(new Solution().inorderTraversal(new TreeNode(1))); // [1]
}
/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();// 0094.2 - Binary Tree Inorder Traversal - Solution 2 - Iterative with Stack
package main
/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"
/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func inorderTraversalIterative(root *TreeNode) []int {
ans := []int{}
stack := []*TreeNode{}
current := root
for current != nil || len(stack) > 0 {
for current != nil {
stack = append(stack, current)
current = current.Left
}
current = stack[len(stack)-1]
stack = stack[:len(stack)-1]
ans = append(ans, current.Val)
current = current.Right
}
return ans
}
func testcase() {
root1 := &TreeNode{Val: 1, Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}}}
fmt.Println(inorderTraversalIterative(root1)) // [1 3 2]
fmt.Println(inorderTraversalIterative(nil)) // []
fmt.Println(inorderTraversalIterative(&TreeNode{Val: 1})) // [1]
}
/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
testcase()
}// 0094.2 - Binary Tree Inorder Traversal - Solution 2 - Iterative with Stack
use std::rc::Rc;
use std::cell::RefCell;
#[derive(Debug)]
struct TreeNode {
val: i32,
left: Option<Rc<RefCell<TreeNode>>>,
right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
fn new(val: i32) -> Rc<RefCell<TreeNode>> {
Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
}
}
struct Solution;
impl Solution {
pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut ans: Vec<i32> = Vec::new();
let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
let mut current = root;
while current.is_some() || !stack.is_empty() {
while let Some(n) = current {
current = n.borrow().left.clone();
stack.push(n);
}
let node = stack.pop().unwrap();
ans.push(node.borrow().val);
current = node.borrow().right.clone();
}
ans
}
}
fn main() {
let root1 = TreeNode::new(1);
let node2 = TreeNode::new(2);
let node3 = TreeNode::new(3);
node2.borrow_mut().left = Some(node3.clone());
root1.borrow_mut().right = Some(node2.clone());
println!("{:?}", Solution::inorder_traversal(Some(root1))); // [1, 3, 2]
}