Recursion in binary trees to return a bool value?





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}







0















I want to create a recursive function that takes a binary tree as its parameter and returns True if every leaf below a node is greater than its parent. If just one node fails to meet this condition, the entire function should return False.



However, I am struggling to come up with a base case, as well as fully understanding how to stop the function and return False if even just one part of the tree does not meet the condition. Any help would be greatly appreciated.






python recursion binary-tree







share|improve this question


















  • 1





    In Python and is short-cutting and hence naturally "stops" the function. Hence you can just and the condition for the two leafs of each node.

    – a_guest
    Nov 24 '18 at 23:31




















0















I want to create a recursive function that takes a binary tree as its parameter and returns True if every leaf below a node is greater than its parent. If just one node fails to meet this condition, the entire function should return False.



However, I am struggling to come up with a base case, as well as fully understanding how to stop the function and return False if even just one part of the tree does not meet the condition. Any help would be greatly appreciated.






python recursion binary-tree







share|improve this question


















  • 1





    In Python and is short-cutting and hence naturally "stops" the function. Hence you can just and the condition for the two leafs of each node.

    – a_guest
    Nov 24 '18 at 23:31
















0












0








0


1






I want to create a recursive function that takes a binary tree as its parameter and returns True if every leaf below a node is greater than its parent. If just one node fails to meet this condition, the entire function should return False.



However, I am struggling to come up with a base case, as well as fully understanding how to stop the function and return False if even just one part of the tree does not meet the condition. Any help would be greatly appreciated.






python recursion binary-tree







share|improve this question














I want to create a recursive function that takes a binary tree as its parameter and returns True if every leaf below a node is greater than its parent. If just one node fails to meet this condition, the entire function should return False.



However, I am struggling to come up with a base case, as well as fully understanding how to stop the function and return False if even just one part of the tree does not meet the condition. Any help would be greatly appreciated.






python recursion binary-tree




python recursion binary-tree






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked Nov 24 '18 at 23:23









B. NguyenB. Nguyen

83




83








  • 1





    In Python and is short-cutting and hence naturally "stops" the function. Hence you can just and the condition for the two leafs of each node.

    – a_guest
    Nov 24 '18 at 23:31
















  • 1





    In Python and is short-cutting and hence naturally "stops" the function. Hence you can just and the condition for the two leafs of each node.

    – a_guest
    Nov 24 '18 at 23:31










1




1





In Python and is short-cutting and hence naturally "stops" the function. Hence you can just and the condition for the two leafs of each node.

– a_guest
Nov 24 '18 at 23:31







In Python and is short-cutting and hence naturally "stops" the function. Hence you can just and the condition for the two leafs of each node.

– a_guest
Nov 24 '18 at 23:31














2 Answers
2






active

oldest

votes


















0














When recurring through the tree, the base case would be a leaf node - that is, a node with no children. For such a node, you would assume that it has met the test (since otherwise, you algorithm should have already returned false), so you would return true.



For the general case, you would want to check if the node is smaller than both it’s children, and if not, return False. Otherwise, to ensure that the condition holds for both children, you would return the result of recurring down the left side and the result of recurring down the right:



return check(node.left) and check(node.right)





share|improve this answer































    0














    Using recursion, something like this should work:



    def children_gt_parent(node, parent_val):
    
    if node is None:
    
        return True
    
    if node.value <= parent_val:
    
        return False
    
    return children_gt_parent(node.left, node.value) and children_gt_parent(node.right, node.value)


    You then call it like:



    tf = children_gt_parent(root, root.value)





    share|improve this answer
























      Your Answer






      StackExchange.ifUsing("editor", function () {
      StackExchange.using("externalEditor", function () {
      StackExchange.using("snippets", function () {
      StackExchange.snippets.init();
      });
      });
      }, "code-snippets");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "1"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53463266%2frecursion-in-binary-trees-to-return-a-bool-value%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      0














      When recurring through the tree, the base case would be a leaf node - that is, a node with no children. For such a node, you would assume that it has met the test (since otherwise, you algorithm should have already returned false), so you would return true.



      For the general case, you would want to check if the node is smaller than both it’s children, and if not, return False. Otherwise, to ensure that the condition holds for both children, you would return the result of recurring down the left side and the result of recurring down the right:



      return check(node.left) and check(node.right)





      share|improve this answer




























        0














        When recurring through the tree, the base case would be a leaf node - that is, a node with no children. For such a node, you would assume that it has met the test (since otherwise, you algorithm should have already returned false), so you would return true.



        For the general case, you would want to check if the node is smaller than both it’s children, and if not, return False. Otherwise, to ensure that the condition holds for both children, you would return the result of recurring down the left side and the result of recurring down the right:



        return check(node.left) and check(node.right)





        share|improve this answer


























          0












          0








          0







          When recurring through the tree, the base case would be a leaf node - that is, a node with no children. For such a node, you would assume that it has met the test (since otherwise, you algorithm should have already returned false), so you would return true.



          For the general case, you would want to check if the node is smaller than both it’s children, and if not, return False. Otherwise, to ensure that the condition holds for both children, you would return the result of recurring down the left side and the result of recurring down the right:



          return check(node.left) and check(node.right)





          share|improve this answer













          When recurring through the tree, the base case would be a leaf node - that is, a node with no children. For such a node, you would assume that it has met the test (since otherwise, you algorithm should have already returned false), so you would return true.



          For the general case, you would want to check if the node is smaller than both it’s children, and if not, return False. Otherwise, to ensure that the condition holds for both children, you would return the result of recurring down the left side and the result of recurring down the right:



          return check(node.left) and check(node.right)






          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered Nov 24 '18 at 23:36









          GniemGniem

          914




          914

























              0














              Using recursion, something like this should work:



              def children_gt_parent(node, parent_val):
              
    if node is None:
              
        return True
              
    if node.value <= parent_val:
              
        return False
              
    return children_gt_parent(node.left, node.value) and children_gt_parent(node.right, node.value)


              You then call it like:



              tf = children_gt_parent(root, root.value)





              share|improve this answer




























                0














                Using recursion, something like this should work:



                def children_gt_parent(node, parent_val):
                
    if node is None:
                
        return True
                
    if node.value <= parent_val:
                
        return False
                
    return children_gt_parent(node.left, node.value) and children_gt_parent(node.right, node.value)


                You then call it like:



                tf = children_gt_parent(root, root.value)





                share|improve this answer


























                  0












                  0








                  0







                  Using recursion, something like this should work:



                  def children_gt_parent(node, parent_val):
                  
    if node is None:
                  
        return True
                  
    if node.value <= parent_val:
                  
        return False
                  
    return children_gt_parent(node.left, node.value) and children_gt_parent(node.right, node.value)


                  You then call it like:



                  tf = children_gt_parent(root, root.value)





                  share|improve this answer













                  Using recursion, something like this should work:



                  def children_gt_parent(node, parent_val):
                  
    if node is None:
                  
        return True
                  
    if node.value <= parent_val:
                  
        return False
                  
    return children_gt_parent(node.left, node.value) and children_gt_parent(node.right, node.value)


                  You then call it like:



                  tf = children_gt_parent(root, root.value)






                  share|improve this answer












                  share|improve this answer



                  share|improve this answer










                  answered Nov 24 '18 at 23:40









                  mnisticmnistic

                  7,24611025




                  7,24611025






























                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Stack Overflow!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid …



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53463266%2frecursion-in-binary-trees-to-return-a-bool-value%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      -

                      這個網誌中的熱門文章

                      Xamarin.form Move up view when keyboard appear

                      圖片
                      .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I'm trying to build a Chat app UI, the idea of the Layout was pretty simple: When the input bar is focused, keyboard show up and "push" up the chat bar, as it's a grid, the ListView will resize to fit the screen: I update the input bar's margin to "push" it up: NSValue result = (NSValue)args.Notification.UserInfo.ObjectForKey(new NSString(UIKeyboard.FrameEndUserInfoKey)); CGSize keyboardSize = result.RectangleFValue.Size; if (Element != null){ Element.Margin = new Thickness(0, 0, 0,keyboardSize.Height); //push the entry up to keyboard height when keyboard is activated } And this is ...
                      閱讀完整內容

                      Post-Redirect-Get with Spring WebFlux and Thymeleaf

                      圖片
                      .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 2 Can someone explain to me how to implement the post-redirect-get pattern in Spring WebFlux and Thymeleaf? What subscribes on the database save method? @GetMapping("/register") public String showRegisterForm(Model model) { model.addAttribute("user", new User()); return "register"; } @PostMapping public String processRegisterForm(@Valid User user, BindingResult bindingResult) { if (bindingResult.hasErrors()) { return "register"; } else { userRepository.save(user); //what subscribes on this? //how to redirect on e.g. "/login"? ...
                      閱讀完整內容

                      Anylogic : not able to use stopDelay()

                      圖片
                      -2 I am building a railway station model. I want a train to depart when I click a button. I want to call stopDelay() for that but I am not sure how to do that and from which place. anylogic share | improve this question asked Nov 23 '18 at 10:12 Anupam Singh Anupam Singh 1 Hi Anupam, welcome to SOF. Please check how to ask good questions, see link below. Your question is...
                      閱讀完整內容