Question about Depth First Search? Confused.

Question

I have been thinking about this question for a couple of days but can’t seem to have an answer. Why is that when you perform a depth-first search on a binary search tree, the keys are in sorted, increasing order

Answer 1

Indeed, that's why the method of traversal you are using here is also known as in-order traversal.

As in a BST, every left subtree would have values less than the value of current node so it is guaranteed that while traversing left subtree first then current node and then right subtree, one would always get an increasing sequence.

Answer 2

Annei ❤️ that depends on how exactly are you performing the depth first search.
Depending on what you perform first when you reach certain node in tree, there are three ways to do so :-

1) preorder traversal : where you first visit current node then visit the left subtree and then right subtree.

2) postorder traversal: where you first visit left subtree, then right subtree and then visit the current node

3) inorder traversal: where you first visit left subtree, then visit current node and then right one. ( Due to the nature of BST, this one yields an increasing sequence as you would always be visiting nodes with lesser value than the current node first and then visit the node with higher values )

Answer 3

but sorry, I have a question Arsenic 😅 Since were enqueuing, wouldn’t the value be going in a descreasing order?

Answer 4

Beautifully explained, Thank you!