How does search work in a tree?

Tree search depends on its structure and the search goal.

Main search methods:

Depth-First Search (DFS): Goes as deep as possible along one branch before moving to the next. Implemented using a stack (explicitly or implicitly through recursion).
- Pre-order traversal: Visit the root, then the left subtree, then the right subtree.
- In-order traversal: Visit the left subtree, then the root, then the right subtree. Used in binary search trees to get a sorted list of elements.
- Post-order traversal: Visit the left subtree, then the right subtree, then the root.
Breadth-First Search (BFS): Explores all neighbors at the current level before moving to the next level. Implemented using a queue.

Example of DFS (In-order) for a binary tree:

// TreeNode represents a node in a binary tree
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal performs inorder traversal
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Recursive call for the left subtree
	result = append(result, InOrderTraversal(root.Left)...)
	// Visit the current node
	result = append(result, root.Val)
	// Recursive call for the right subtree
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Example of BFS:

// TreeNode represents a node in a binary tree
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal performs BFS traversal
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Queue to hold nodes at the current level
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Dequeue the first element
		node := queue[0]
		queue = queue[1:]

		// Add the node's value to the result
		result = append(result, node.Val)

		// Enqueue left child if it exists
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Enqueue right child if it exists
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

For binary search trees (BST), where the left subtree is less than the root and the right is greater:

Binary Search: When searching for a specific value, compare it with the root. If less, search in the left subtree; if greater, search in the right subtree. This is the most efficient search strategy in BST.

// TreeNode represents a node in a binary search tree
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST performs binary search in a BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Node found or tree is empty
	}

	if target < root.Val {
		// Search in the left subtree
		return SearchBST(root.Left, target)
	}
	// Search in the right subtree
	return SearchBST(root.Right, target)
}

The choice of search algorithm depends on the task and the tree's characteristics. DFS is suitable for deep traversal or pathfinding, BFS for shortest path or level-order traversal, and binary search for efficient lookup in sorted structures like BST.