I need assistance with responding to this discussion: Which of the traversals are depth-first? Which are breadth-first?
Question:
I need assistance with responding to this discussion:
Which of the traversals are depth-first? Which are breadth-first?
Binary trees have three essential components, the root, the left-subtree, and the right-subtree. So traversing the components requires a traversal method and there are four main methods using either depth first search or breadth first search. Traversals with depth first searches (DFS) are inorder, pre-order, post-order. Breadth first searches (BFS) are level-order traversals.
Which of the traversals lend themselves to recursive solutions? Why are those solutions much simpler than their iterative counterparts?
A binary tree itself is a recursive object so the traversals inorder, preorder, and post order, and level-order require recursive implementation.
- Choose one type of tree traversal and give an example of a situation, in which it would be useful.
The most obvious type of tree traversal would be a family tree. I'm sure ancestry.com uses many Binary trees to keep track of genealogy & family history.
RESPOND HERE:
NEXT : MY RESPONSE: Which of the traversals are depth-first? Which are breadth-first?
Beginning with the root node, the algorithm explores each branch before reversing direction. Utilizing stacks in its implementation. When writing code, we typically leverage recursion stacks to go back. By leveraging recursion, we can take advantage of the fact that the left and right subtrees are both trees with comparable features.
For binary trees, there are three possible DFS traversals.
- In-Order
- Pre-Order
- Post-Order
This process visits each node level by level, beginning with the root node. This means that all immediate descendants of the root are traversed following the root. After crossing all of the root's immediate children continues to their children and so on. We employ a queue to carry out BFS. We have Level Order Traversal for binary trees, which follows after BFS.
- Which kind of traversal of a binary search tree produces the values in sorted order?
An essential aspect of Binary Search Trees is that the left child node is always smaller than its parent and the right child node is always larger than its parent (BSTs). An in-order traversal first explores/prints the node's left child, then the node itself, and lastly the node's right child. Because dealing with a node's left child before the node itself indicates that the leftmost leaf node will be displayed first, followed by its parent, and so on, the values are entered in the correct sequence. For example, in the tree below, start at G (the root), then move to C (G's left child), and ultimately to B. We'd publish B and return to C because B has no left kid. Because C's left child has already been addressed, we'll skip C and go on to F. We'd print F first if it had a left child, but because it doesn't, we'll keep printing F until the tree is complete.
G
/
C P
/ /
B F J Y
M
It is preferable to do preorder traversal recursively, as doing so iteratively would necessitate additional data structure to keep account of previous steps.
RESPOND TO THIS QUESTION: Could you please improve tree layout and list it's preorder, inorder and postorder traversals?
Expert Answer:
