data structures - Why in-order traversal of a threaded tree is O(N)? -

i can't seem figure out how in-order traversal of threaded binary tree o(n).. because have descend links find the leftmost child , go thread when want add parent traversal path. not o(n^2)?

thanks!

the traversal of tree (threaded or not) o(n) because visiting node, starting parent, o(1). visitation of node consists of 3 fixed operations: descending node parent, visitation proper (spending time @ node), , returning parent. o(1 * n) o(n).

the ultimate way @ tree graph, , traversal crosses each edge in graph twice. , number of edges proportional number of nodes since there no cycles or redundant edges (each node can reached 1 unique path). tree n nodes has n-1 edges: each node has edge leading parent node, except root node of tree.

at times appears if visiting node requires more 1 descent. instance, after visiting rightmost node in subtree, have pop numerous levels before can march right next subtree. did not descend way down visit that node. each one-level descent can accounted being necessary visiting node below, , opposite ascent's cost lumped that. visiting node v, gain access nodes below it, nodes benefit , share edge traversal v's parent down v, , again.

this related amortized analysis, applies in situations can globally understand overall cost based on general observation structure of problem, @ detailed level of individual operations, costs distributed in uneven way appears confusing.

amortized analysis helps understand that, instance, n insertions hash table resizes growing exponentially o(n). of insertion operations quick, time time, grow table , process contents. similar how, time time during tree traversal, have perform numerous consecutive ascents climb out of deep subtree.

the global observation hash table each item inserted table move larger table on average 3 times in 3 resize operations, , each insertion can regarded "pre paying" 3 re-insertions, fixed cost. of course, "older" items moved more times, offset "younger" entries move fewer times, diluting cost. , global observation tree noted above: has n-1 edges, each of traversed twice during traversal, visitation of each node "pays" double traversal of respective edge. because easy see, don't have formally apply amortized analysis tree traversal.

now suppose performed individual searches each node (and tree balanced search tree). traversal still not o(n*n), rather o(n log n). suppose have ordered search tree holds consecutive integers. if increment on integers , perform individual searches each value, each search o(log n), , end doing n of these. in situation, edge traversals no longer shared, amortization not apply. reach given node searching found @ depth d, have cross d edges twice, sake of node , node alone. next search in loop integer independent of previous one.

it may think of linked list, can regarded unbalanced tree. visit items in linked list of length n , return head node o(n). searching each item individually o(n*n), in traversal, not searching each node individually, using each predecessor springboard finding next node.