Mixing
Proving Postorder Traversal's Time Complexity
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I am looking at the following algorithm for performing a Postorder Traversal of a binary tree
POSTORDER(root):
if root != nullthen
POSTORDER(root.left);
POSTORDER(root.right);
visit root;
end if;
I am supposed to be able to demonstrate that this algorithm runs in Θ(n) time complexity when the input is a n-vertex tree. But I am not even sure where to begin with doing that.
I have looked at the following sources:
- https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
- https://en.wikipedia.org/wiki/Reverse_Polish_notation
- https://en.wikipedia.org/wiki/Tree_traversal
- https://leetcode.com/articles/introduction-to-n-ary-trees/
I understand WHAT PostOrder traversal does, and I understand WHAT a binary tree is, but I don't know how I can prove that time complexity.
Could anybody help me on this?
algorithms algorithm-analysis binary-trees graph-traversal
edited Sep 4 at 13:52
Jot Waraich
30110
add a comment |Â
up vote
2
down vote
favorite
I am looking at the following algorithm for performing a Postorder Traversal of a binary tree
POSTORDER(root):
if root != nullthen
POSTORDER(root.left);
POSTORDER(root.right);
visit root;
end if;
I am supposed to be able to demonstrate that this algorithm runs in Θ(n) time complexity when the input is a n-vertex tree. But I am not even sure where to begin with doing that.
I have looked at the following sources:
- https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
- https://en.wikipedia.org/wiki/Reverse_Polish_notation
- https://en.wikipedia.org/wiki/Tree_traversal
- https://leetcode.com/articles/introduction-to-n-ary-trees/
I understand WHAT PostOrder traversal does, and I understand WHAT a binary tree is, but I don't know how I can prove that time complexity.
Could anybody help me on this?
algorithms algorithm-analysis binary-trees graph-traversal
edited Sep 4 at 13:52
Jot Waraich
30110
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I am looking at the following algorithm for performing a Postorder Traversal of a binary tree
POSTORDER(root):
if root != nullthen
POSTORDER(root.left);
POSTORDER(root.right);
visit root;
end if;
I am supposed to be able to demonstrate that this algorithm runs in Θ(n) time complexity when the input is a n-vertex tree. But I am not even sure where to begin with doing that.
I have looked at the following sources:
- https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
- https://en.wikipedia.org/wiki/Reverse_Polish_notation
- https://en.wikipedia.org/wiki/Tree_traversal
- https://leetcode.com/articles/introduction-to-n-ary-trees/
I understand WHAT PostOrder traversal does, and I understand WHAT a binary tree is, but I don't know how I can prove that time complexity.
Could anybody help me on this?
algorithms algorithm-analysis binary-trees graph-traversal
edited Sep 4 at 13:52
Jot Waraich
30110
I am looking at the following algorithm for performing a Postorder Traversal of a binary tree
POSTORDER(root):
if root != nullthen
POSTORDER(root.left);
POSTORDER(root.right);
visit root;
end if;
I am supposed to be able to demonstrate that this algorithm runs in Θ(n) time complexity when the input is a n-vertex tree. But I am not even sure where to begin with doing that.
I have looked at the following sources:
- https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
- https://en.wikipedia.org/wiki/Reverse_Polish_notation
- https://en.wikipedia.org/wiki/Tree_traversal
- https://leetcode.com/articles/introduction-to-n-ary-trees/
I understand WHAT PostOrder traversal does, and I understand WHAT a binary tree is, but I don't know how I can prove that time complexity.
Could anybody help me on this?
algorithms algorithm-analysis binary-trees graph-traversal
edited Sep 4 at 13:52
Jot Waraich
30110
edited Sep 4 at 13:52
Jot Waraich
30110
edited Sep 4 at 13:52
Jot Waraich
30110
edited Sep 4 at 13:52
Jot Waraich
30110
30110
asked Sep 3 at 17:56
user93381
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
In order to prove the complexity of n-vertex tree, you must first understand how to analyze the time for a binary tree. So i am explaining it for a binary tree so that you can generalize it.
In postorder traversal each node in binary tree is visited:
a) 1 time if it is a leaf node.
b) 1 time if it is a node with only one child (either left or right)
c) 2 times if the node has both left and right children. 2 times because when we have to process the right child once we have finished with processing of its left child we need to check whether the node has right child or not. If it has a right child we process right child deferring the parent node so that it could be revisited again once we are finished with processing of right child as well.
So, any node in the tree is not visited more than two times. If n is the number of nodes then the worst case complexity is $O(2n)$ (in case of complete binary tree) and best case is $O(n)$ (in case of skew tree). Ignoring the constants:
Best case time : $O(n)$
Worst case time : $O(n)$
Hence, we can say algorithm is $Θ(n)$.
answered Sep 3 at 18:33
Jot Waraich
30110
Jot, thank you very much for this detailed explanation. This made a LOT of sense to me, especially in your simplified format. I appreciate you teaching me.
– user93381
Sep 3 at 19:30
No problem at all but since you are new to this platform i will tell you that you need not say thanks to anyone and comments are for clarification only.
– Jot Waraich
Sep 3 at 20:30
add a comment |Â
up vote
1
down vote
Show that POSTORDER(v) will at most be called exactly once for each vertex v.
This can be done via Induction by depth:
- First show that
POSTORDER(root)will only be called once (depth 0). This is easy, since there doesn't exist a parent ofroot, therefore there exists no nodevwithv.left == rootorv.right == root. - Then assume that
POSTORDER(v)will be called exactly once for every node at depth $n$, and show that this is also true for every vertex at depth $n + 1$. This should be straightforward to prove.
Since, other than the recursive calls (which we already understand), we do only constant stuff in a call of POSTORDER(v), the time complexity is $Theta(n) cdot Theta(1) = Theta(n)$.
answered Sep 3 at 18:45
Jakube
63019
Jakube, thank you very much for your answer. This seemingly makes sense. I guess my question is, and I know this is probably elementary and annoying, how is it possible to "prove" via induction that the POSTORDER call can only be made once for every vertex at depth (n+1)? Also, where does the theta(1) portion of complexity come from?
– user93381
Sep 3 at 19:18
A callPOSTORDER(v)can only come from a parent nodep. The parent node is at depth $n$, therefore via induction we know thatponly gets visited once. Therefore so doesv.
– Jakube
Sep 3 at 19:29
The $Theta(1)$ stuff is theifandvisitoperation. They take constant time.
– Jakube
Sep 3 at 19:30
I actually forgot thePOSTORDER(null)calls. You can easily show that there are at most $n$ of those. Which doesn't hurt your complexity.
– Jakube
Sep 3 at 19:31
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
In order to prove the complexity of n-vertex tree, you must first understand how to analyze the time for a binary tree. So i am explaining it for a binary tree so that you can generalize it.
In postorder traversal each node in binary tree is visited:
a) 1 time if it is a leaf node.
b) 1 time if it is a node with only one child (either left or right)
c) 2 times if the node has both left and right children. 2 times because when we have to process the right child once we have finished with processing of its left child we need to check whether the node has right child or not. If it has a right child we process right child deferring the parent node so that it could be revisited again once we are finished with processing of right child as well.
So, any node in the tree is not visited more than two times. If n is the number of nodes then the worst case complexity is $O(2n)$ (in case of complete binary tree) and best case is $O(n)$ (in case of skew tree). Ignoring the constants:
Best case time : $O(n)$
Worst case time : $O(n)$
Hence, we can say algorithm is $Θ(n)$.
answered Sep 3 at 18:33
Jot Waraich
30110
Jot, thank you very much for this detailed explanation. This made a LOT of sense to me, especially in your simplified format. I appreciate you teaching me.
– user93381
Sep 3 at 19:30
No problem at all but since you are new to this platform i will tell you that you need not say thanks to anyone and comments are for clarification only.
– Jot Waraich
Sep 3 at 20:30
add a comment |Â
up vote
1
down vote
accepted
In order to prove the complexity of n-vertex tree, you must first understand how to analyze the time for a binary tree. So i am explaining it for a binary tree so that you can generalize it.
In postorder traversal each node in binary tree is visited:
a) 1 time if it is a leaf node.
b) 1 time if it is a node with only one child (either left or right)
c) 2 times if the node has both left and right children. 2 times because when we have to process the right child once we have finished with processing of its left child we need to check whether the node has right child or not. If it has a right child we process right child deferring the parent node so that it could be revisited again once we are finished with processing of right child as well.
So, any node in the tree is not visited more than two times. If n is the number of nodes then the worst case complexity is $O(2n)$ (in case of complete binary tree) and best case is $O(n)$ (in case of skew tree). Ignoring the constants:
Best case time : $O(n)$
Worst case time : $O(n)$
Hence, we can say algorithm is $Θ(n)$.
answered Sep 3 at 18:33
Jot Waraich
30110
Jot, thank you very much for this detailed explanation. This made a LOT of sense to me, especially in your simplified format. I appreciate you teaching me.
– user93381
Sep 3 at 19:30
No problem at all but since you are new to this platform i will tell you that you need not say thanks to anyone and comments are for clarification only.
– Jot Waraich
Sep 3 at 20:30
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
In order to prove the complexity of n-vertex tree, you must first understand how to analyze the time for a binary tree. So i am explaining it for a binary tree so that you can generalize it.
In postorder traversal each node in binary tree is visited:
a) 1 time if it is a leaf node.
b) 1 time if it is a node with only one child (either left or right)
c) 2 times if the node has both left and right children. 2 times because when we have to process the right child once we have finished with processing of its left child we need to check whether the node has right child or not. If it has a right child we process right child deferring the parent node so that it could be revisited again once we are finished with processing of right child as well.
So, any node in the tree is not visited more than two times. If n is the number of nodes then the worst case complexity is $O(2n)$ (in case of complete binary tree) and best case is $O(n)$ (in case of skew tree). Ignoring the constants:
Best case time : $O(n)$
Worst case time : $O(n)$
Hence, we can say algorithm is $Θ(n)$.
answered Sep 3 at 18:33
Jot Waraich
30110
In order to prove the complexity of n-vertex tree, you must first understand how to analyze the time for a binary tree. So i am explaining it for a binary tree so that you can generalize it.
In postorder traversal each node in binary tree is visited:
a) 1 time if it is a leaf node.
b) 1 time if it is a node with only one child (either left or right)
c) 2 times if the node has both left and right children. 2 times because when we have to process the right child once we have finished with processing of its left child we need to check whether the node has right child or not. If it has a right child we process right child deferring the parent node so that it could be revisited again once we are finished with processing of right child as well.
So, any node in the tree is not visited more than two times. If n is the number of nodes then the worst case complexity is $O(2n)$ (in case of complete binary tree) and best case is $O(n)$ (in case of skew tree). Ignoring the constants:
Best case time : $O(n)$
Worst case time : $O(n)$
Hence, we can say algorithm is $Θ(n)$.
answered Sep 3 at 18:33
Jot Waraich
30110
edited Sep 3 at 18:52
answered Sep 3 at 18:33
Jot Waraich
30110
answered Sep 3 at 18:33
Jot Waraich
30110
answered Sep 3 at 18:33
Jot Waraich
30110
30110
Jot, thank you very much for this detailed explanation. This made a LOT of sense to me, especially in your simplified format. I appreciate you teaching me.
– user93381
Sep 3 at 19:30
No problem at all but since you are new to this platform i will tell you that you need not say thanks to anyone and comments are for clarification only.
– Jot Waraich
Sep 3 at 20:30
add a comment |Â
Jot, thank you very much for this detailed explanation. This made a LOT of sense to me, especially in your simplified format. I appreciate you teaching me.
– user93381
Sep 3 at 19:30
No problem at all but since you are new to this platform i will tell you that you need not say thanks to anyone and comments are for clarification only.
– Jot Waraich
Sep 3 at 20:30
Jot, thank you very much for this detailed explanation. This made a LOT of sense to me, especially in your simplified format. I appreciate you teaching me.
– user93381
Sep 3 at 19:30
Jot, thank you very much for this detailed explanation. This made a LOT of sense to me, especially in your simplified format. I appreciate you teaching me.
– user93381
Sep 3 at 19:30
No problem at all but since you are new to this platform i will tell you that you need not say thanks to anyone and comments are for clarification only.
– Jot Waraich
Sep 3 at 20:30
No problem at all but since you are new to this platform i will tell you that you need not say thanks to anyone and comments are for clarification only.
– Jot Waraich
Sep 3 at 20:30
add a comment |Â
up vote
1
down vote
Show that POSTORDER(v) will at most be called exactly once for each vertex v.
This can be done via Induction by depth:
- First show that
POSTORDER(root)will only be called once (depth 0). This is easy, since there doesn't exist a parent ofroot, therefore there exists no nodevwithv.left == rootorv.right == root. - Then assume that
POSTORDER(v)will be called exactly once for every node at depth $n$, and show that this is also true for every vertex at depth $n + 1$. This should be straightforward to prove.
Since, other than the recursive calls (which we already understand), we do only constant stuff in a call of POSTORDER(v), the time complexity is $Theta(n) cdot Theta(1) = Theta(n)$.
answered Sep 3 at 18:45
Jakube
63019
Jakube, thank you very much for your answer. This seemingly makes sense. I guess my question is, and I know this is probably elementary and annoying, how is it possible to "prove" via induction that the POSTORDER call can only be made once for every vertex at depth (n+1)? Also, where does the theta(1) portion of complexity come from?
– user93381
Sep 3 at 19:18
A callPOSTORDER(v)can only come from a parent nodep. The parent node is at depth $n$, therefore via induction we know thatponly gets visited once. Therefore so doesv.
– Jakube
Sep 3 at 19:29
The $Theta(1)$ stuff is theifandvisitoperation. They take constant time.
– Jakube
Sep 3 at 19:30
I actually forgot thePOSTORDER(null)calls. You can easily show that there are at most $n$ of those. Which doesn't hurt your complexity.
– Jakube
Sep 3 at 19:31
add a comment |Â
up vote
1
down vote
Show that POSTORDER(v) will at most be called exactly once for each vertex v.
This can be done via Induction by depth:
- First show that
POSTORDER(root)will only be called once (depth 0). This is easy, since there doesn't exist a parent ofroot, therefore there exists no nodevwithv.left == rootorv.right == root. - Then assume that
POSTORDER(v)will be called exactly once for every node at depth $n$, and show that this is also true for every vertex at depth $n + 1$. This should be straightforward to prove.
Since, other than the recursive calls (which we already understand), we do only constant stuff in a call of POSTORDER(v), the time complexity is $Theta(n) cdot Theta(1) = Theta(n)$.
answered Sep 3 at 18:45
Jakube
63019
Jakube, thank you very much for your answer. This seemingly makes sense. I guess my question is, and I know this is probably elementary and annoying, how is it possible to "prove" via induction that the POSTORDER call can only be made once for every vertex at depth (n+1)? Also, where does the theta(1) portion of complexity come from?
– user93381
Sep 3 at 19:18
A callPOSTORDER(v)can only come from a parent nodep. The parent node is at depth $n$, therefore via induction we know thatponly gets visited once. Therefore so doesv.
– Jakube
Sep 3 at 19:29
The $Theta(1)$ stuff is theifandvisitoperation. They take constant time.
– Jakube
Sep 3 at 19:30
I actually forgot thePOSTORDER(null)calls. You can easily show that there are at most $n$ of those. Which doesn't hurt your complexity.
– Jakube
Sep 3 at 19:31
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Show that POSTORDER(v) will at most be called exactly once for each vertex v.
This can be done via Induction by depth:
- First show that
POSTORDER(root)will only be called once (depth 0). This is easy, since there doesn't exist a parent ofroot, therefore there exists no nodevwithv.left == rootorv.right == root. - Then assume that
POSTORDER(v)will be called exactly once for every node at depth $n$, and show that this is also true for every vertex at depth $n + 1$. This should be straightforward to prove.
Since, other than the recursive calls (which we already understand), we do only constant stuff in a call of POSTORDER(v), the time complexity is $Theta(n) cdot Theta(1) = Theta(n)$.
answered Sep 3 at 18:45
Jakube
63019
Show that POSTORDER(v) will at most be called exactly once for each vertex v.
This can be done via Induction by depth:
- First show that
POSTORDER(root)will only be called once (depth 0). This is easy, since there doesn't exist a parent ofroot, therefore there exists no nodevwithv.left == rootorv.right == root. - Then assume that
POSTORDER(v)will be called exactly once for every node at depth $n$, and show that this is also true for every vertex at depth $n + 1$. This should be straightforward to prove.
Since, other than the recursive calls (which we already understand), we do only constant stuff in a call of POSTORDER(v), the time complexity is $Theta(n) cdot Theta(1) = Theta(n)$.
answered Sep 3 at 18:45
Jakube
63019
answered Sep 3 at 18:45
Jakube
63019
answered Sep 3 at 18:45
Jakube
63019
answered Sep 3 at 18:45
Jakube
63019
63019
Jakube, thank you very much for your answer. This seemingly makes sense. I guess my question is, and I know this is probably elementary and annoying, how is it possible to "prove" via induction that the POSTORDER call can only be made once for every vertex at depth (n+1)? Also, where does the theta(1) portion of complexity come from?
– user93381
Sep 3 at 19:18
A callPOSTORDER(v)can only come from a parent nodep. The parent node is at depth $n$, therefore via induction we know thatponly gets visited once. Therefore so doesv.
– Jakube
Sep 3 at 19:29
The $Theta(1)$ stuff is theifandvisitoperation. They take constant time.
– Jakube
Sep 3 at 19:30
I actually forgot thePOSTORDER(null)calls. You can easily show that there are at most $n$ of those. Which doesn't hurt your complexity.
– Jakube
Sep 3 at 19:31
add a comment |Â
Jakube, thank you very much for your answer. This seemingly makes sense. I guess my question is, and I know this is probably elementary and annoying, how is it possible to "prove" via induction that the POSTORDER call can only be made once for every vertex at depth (n+1)? Also, where does the theta(1) portion of complexity come from?
– user93381
Sep 3 at 19:18
A callPOSTORDER(v)can only come from a parent nodep. The parent node is at depth $n$, therefore via induction we know thatponly gets visited once. Therefore so doesv.
– Jakube
Sep 3 at 19:29
The $Theta(1)$ stuff is theifandvisitoperation. They take constant time.
– Jakube
Sep 3 at 19:30
I actually forgot thePOSTORDER(null)calls. You can easily show that there are at most $n$ of those. Which doesn't hurt your complexity.
– Jakube
Sep 3 at 19:31
Jakube, thank you very much for your answer. This seemingly makes sense. I guess my question is, and I know this is probably elementary and annoying, how is it possible to "prove" via induction that the POSTORDER call can only be made once for every vertex at depth (n+1)? Also, where does the theta(1) portion of complexity come from?
– user93381
Sep 3 at 19:18
Jakube, thank you very much for your answer. This seemingly makes sense. I guess my question is, and I know this is probably elementary and annoying, how is it possible to "prove" via induction that the POSTORDER call can only be made once for every vertex at depth (n+1)? Also, where does the theta(1) portion of complexity come from?
– user93381
Sep 3 at 19:18
A call
POSTORDER(v) can only come from a parent node p. The parent node is at depth $n$, therefore via induction we know that p only gets visited once. Therefore so does v.– Jakube
Sep 3 at 19:29
A call
POSTORDER(v) can only come from a parent node p. The parent node is at depth $n$, therefore via induction we know that p only gets visited once. Therefore so does v.– Jakube
Sep 3 at 19:29
The $Theta(1)$ stuff is the
if and visit operation. They take constant time.– Jakube
Sep 3 at 19:30
The $Theta(1)$ stuff is the
if and visit operation. They take constant time.– Jakube
Sep 3 at 19:30
I actually forgot the
POSTORDER(null) calls. You can easily show that there are at most $n$ of those. Which doesn't hurt your complexity.– Jakube
Sep 3 at 19:31
I actually forgot the
POSTORDER(null) calls. You can easily show that there are at most $n$ of those. Which doesn't hurt your complexity.– Jakube
Sep 3 at 19:31
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f96924%2fproving-postorder-traversals-time-complexity%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
