Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T .

Question

Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T .

I have no idea what this question is even asking me. What the hell does -> list(T) even mean?

Answer 1

Look at the binary tree T below.

inorder(T) is a function that does an inorder traversal of a binary tree and collects the nodes in a list L in the order in which they are visited.

That is, inorder(T) returns a list L = [A, B, C, D, E, F, G, H, I]

Now, define T.root to be the root node of T. This would be F.

Define List(node) to be a list containing node.
That is, List(node) = [node]

Define T.left and T.right to be the left and right subtrees of T.
This would be the trees rooted at B and G respectively.

inorder(T.left) would return L1 = [A, B, C, D, E]
inorder(T.right) would return L2 = [G, H, I]

Now a recursive definition of inorder(T) would be:

inorder(T) = inorder(T.left) + List(T.root) + inorder(T.right)

Hope that helps.